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.
1.7K Downloads
Updated 1 Mar 2013

View License

[ 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
Created with R2010b
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes
1.4.0.0

I have fixed a bug that deleted the entire candidates list instead of just the k^th shortest path.

1.1.0.0

I have clarified the description by highlighting the fact that this is an undirected version of the algorithm.

1.0.0.0