Code covered by the BSD License

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

4.0

4.0 | 4 ratings Rate this file 23 Downloads (last 30 days) File Size: 2.2 KB File ID: #35397

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

01 Mar 2012 (Updated )

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

File Information
Description

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

Required Products Bioinformatics Toolbox
MATLAB release MATLAB 7.11 (R2010b)
19 Feb 2013

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

19 Feb 2013

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

19 Feb 2013

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

27 Nov 2012

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.

27 Nov 2012
26 Nov 2012

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

26 Nov 2012

Not intact

16 Jul 2012