File Exchange

## 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

Updated

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

Giorgos Chochlidakis

### El-ad David Amir (view profile)

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

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

### El-ad David Amir (view profile)

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

Qiu

Not intact

hamed veisi