K shortest paths in a graph represented by a sparse matrix (Yen's algorithm)
Determine the K shortest paths from node S to node T.
You are now following this Submission
- You will see updates in your followed content feed
- You may receive emails, depending on your communication preferences
[ 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 (2026). K shortest paths in a graph represented by a sparse matrix (Yen's algorithm) (https://uk.mathworks.com/matlabcentral/fileexchange/35397-k-shortest-paths-in-a-graph-represented-by-a-sparse-matrix-yen-s-algorithm), MATLAB Central File Exchange. Retrieved .
General Information
- Version 1.4.0.0 (2.2 KB)
MATLAB Release Compatibility
- Compatible with any release
Platform Compatibility
- Windows
- macOS
- Linux
