Code covered by the BSD License

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

4.33333
4.3 | 5 ratings Rate this file 30 Downloads (last 30 days) File Size: 2.2 KB File ID: #35397 Version: 1.4

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

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

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)
17 Jun 2014 Giorgos Chochlidakis

### Giorgos Chochlidakis (view profile)

19 Feb 2013 El-ad David Amir

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

Comment only
19 Feb 2013 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; ?

Comment only
19 Feb 2013 Javier Montoya

### Javier Montoya (view profile)

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

Comment only
27 Nov 2012 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.

27 Nov 2012 Qiu

### Qiu (view profile)

26 Nov 2012 El-ad David Amir

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

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

Comment only
26 Nov 2012 Qiu

### Qiu (view profile)

Not intact

16 Jul 2012 hamed veisi