4.33333

4.3 | 5 ratings Rate this file 47 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)

by

 

01 Mar 2012 (Updated )

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

| Watch this File

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)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (9)
17 Jun 2014 Giorgos Chochlidakis  
19 Feb 2013 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.

19 Feb 2013 Javier Montoya

@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 Javier Montoya

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

27 Nov 2012 Qiu

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

27 Nov 2012 Qiu  
26 Nov 2012 El-ad David Amir

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

26 Nov 2012 Qiu

Not intact

16 Jul 2012 hamed veisi  
Updates
01 Mar 2013

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

01 Mar 2013

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

Contact us