feat: Implement Yen's Algorithm for K-Shortest Paths #625
+160
−3
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
- Added Yen's Algorithm implementation to find the K shortest paths between two nodes in a graph. - Supports applications in network routing, transportation planning, and logistics. - Includes test cases to validate the correctness of the implementation. - Optimized for performance and usability within the graph algorithms module.
czgdp1807
reviewed
Mar 11, 2025
| @@ -11,6 +11,8 @@ | |||
| from pydatastructs.graphs.graph import Graph | |||
| from pydatastructs.linear_data_structures.algorithms import merge_sort_parallel | |||
| from pydatastructs import PriorityQueue | |||
| from copy import deepcopy | |||
| import heapq | |||
There was a problem hiding this comment.
We do have heapq implemented in PyDataStructs? I think PriorityQueue and heapq are the same?
| from pydatastructs.utils.raises_util import raises | ||
| import pytest |
There was a problem hiding this comment.
We don't need to import this.
| for i, path in enumerate(k_shortest_paths): | ||
| assert path == expected_paths[i], f"Path {i} does not match expected path. Got {path}, expected {expected_paths[i]}" | ||
|
|
||
| _test_yen_algorithm("List") |
There was a problem hiding this comment.
Why don't we support matrix representation of graphs?
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
✨ Feature: Yen's Algorithm for K-Shortest Paths
FIXES: #622
📌 Description
This PR introduces Yen's Algorithm, which finds the K shortest paths between a source and destination node in a graph. The algorithm efficiently computes multiple alternative paths, making it useful for applications such as:
🛠️ Changes