File Exchange

image thumbnail

K shortest paths in a graph represented by a sparse matrix (Yen's algorithm)

version 1.4 (2.2 KB) by

Determine the K shortest paths from node S to node T.

4.33333
5 Ratings

16 Downloads

Updated

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.

Comments and Ratings (9)

El-ad David Amir

@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.

Javier Montoya

Javier Montoya (view profile)

@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; ?

Javier Montoya

Javier Montoya (view profile)

@El-ad David Amir, By symmetric graphs I was referring to undirected graphs ;-)

Qiu

Qiu (view profile)

@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

Qiu (view profile)

El-ad David Amir

@Qiu: What do you mean by "not intact"?

Qiu

Qiu (view profile)

Not intact

hamed veisi

Updates

1.4

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

1.1

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

MATLAB Release
MATLAB 7.11 (R2010b)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video