View License

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

» Watch video

Highlights from
K-Shortest Path- Yen's algorithm

Join the 15-year community celebration.

Play games and win prizes!

» Learn more

3.8
3.8 | 5 ratings Rate this file 23 Downloads (last 30 days) File Size: 11.6 KB File ID: #32513 Version: 1.0

K-Shortest Path- Yen's algorithm

by

Meral Sh. (view profile)

 

Based on Yen’s algorithm, returns the K shortest paths between a source and a destination.

| Watch this File

File Information
Description

This function is based on Yen's k-Shortest Path algorithm:
J. Y. Yen, "Finding the K shortest loopless paths in a network", Management Science 17:712–716, 1971.

It returns:
1) [shortestPaths]: the list of K shortest paths (in cell array 1xK)
2) [totalCosts] : costs of the K shortest paths (in array 1xK)
Yen's algorithm prevents loops.

This function calls a slightly modified/simplified function dijkstra() (submitted by Xiaodong Wang, 2004)

The Network/Graph of N nodes is fed in the form of a NXN netCostMatrix which must have positive weights/costs.

IMPORTANT: see 'TestKShortestPath.m' and 'Test graph (case 1).pdf' for netCostMatrix format.

MATLAB release MATLAB 7.8 (R2009a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (7)
25 Aug 2016 Sulimon Sattari

Thanks for the file! I've been looking for a way to compute "all" shortest paths between two nodes and this gives me a way to do so.

I was able to speed the code up considerably (about a factor of 10) by pre-allocating "temp" in dijkstra.m, this is simply heeding MATLAB's warning to preallocate for speed. I'd recommend doing the same if anyone is bogged down with larger networks.

17 Mar 2016 Yuxuan Liang

It cost much time in large matrix, omg

17 Nov 2015 Umer Rasheed

Takes a very very long time to compute if matrix is large.

Comment only
15 Feb 2014 Mohammed

Hello I'm new to Matlab, so can any one please tell me how to pass input argument for this code.?

Comment only
23 Sep 2012 zhou jianshan

Thank you for your sharing!

09 Aug 2012 mohammed sportman

it is correct (when i run it some problem appear

03 Dec 2011 Jort Gemmeke

Works like a charm. And as far as I could see, the only shortest path algorithm on File Exchange that returns an N-best list.

Contact us