[ 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.
@Javier Montoya: This is an implementation of the undirected version of Yen's algorithm. I would suspect that several changes will be needed to make it directed; the line you mentioned should probably be deleted, among other alterations.
@El-ad David Amir, I guess, that you're considering the sG sparse graph as being undirected (symmetric), right?
In case of directed graph, then following line should not be used, right
=> k_G( j_next_node, i_node ) = 0; ?
@El-ad David Amir, By symmetric graphs I was referring to undirected graphs ;-)
@El-ad David Amir
Some function ur script used is missing in my matlab, I thought is a intact, but now, I fix the problem. Sorry for the misunderstanding, thanks for your reply.
@Qiu: What do you mean by "not intact"?
I have fixed a bug that deleted the entire candidates list instead of just the k^th shortest path.
I have clarified the description by highlighting the fact that this is an undirected version of the algorithm.
Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.