K shortest paths in a graph represented by a sparse matrix (Yen's algorithm)
[ DIST, PATH ] = graphkshortestpaths( G, S, T, K ) determines the K shortest paths from node S to node T. weights of the edges are all positive entries in the n-by-n adjacency matrix represented by the sparse matrix G. DIST are the K distances from S to T; PATH is a cell array with the K shortest paths themselves.
the shortest path algorithm used is Dijkstra's algorithm (graphshortestpath).
**Please note that the algorithm implemented here is an undirected version of Yen's algorithm**
- Yen, JY. Finding the k shortest loopless paths in a network; Management Science 17(11):712-6.
03/01/2013: I would like to thank Oskar Blom Göransson for helping me find a bug in the previous version.
Cite As
El-ad David Amir (2024). K shortest paths in a graph represented by a sparse matrix (Yen's algorithm) (https://www.mathworks.com/matlabcentral/fileexchange/35397-k-shortest-paths-in-a-graph-represented-by-a-sparse-matrix-yen-s-algorithm), MATLAB Central File Exchange. Retrieved .
MATLAB Release Compatibility
Platform Compatibility
Windows macOS LinuxCategories
- MATLAB > Mathematics > Sparse Matrices >
- MATLAB > Mathematics > Graph and Network Algorithms > Modify Nodes and Edges > Dijkstra algorithm >
Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!Discover Live Editor
Create scripts with code, output, and formatted text in a single executable document.