File Exchange

image thumbnail

K-Shortest Path- Yen's algorithm

version 1.0.0.0 (11.6 KB) by Meral Sh.
Based on Yen’s algorithm, returns the K shortest paths between a source and a destination.

14 Downloads

Updated 12 Aug 2011

View License

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.

Cite As

Meral Sh. (2021). K-Shortest Path- Yen's algorithm (https://www.mathworks.com/matlabcentral/fileexchange/32513-k-shortest-path-yen-s-algorithm), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (20)

navanit dubey

can please someone tell me how to use this function pleaasseee...

长方 姬

for me, 55 points, it's fast, great toolbox.

slimane charafeddine

is it possible to transform this code to stop when the path exceeds a length L ??

slimane charafeddine

I want to know the exact time complexity of this algorithm if it is possible (with the modifications made) Thank you very much it is urgent

Morton O'Kelly

David

Mostafa Ayaz

The nicest toolbox ever created!

mohammad javad majidi

William Clelland

As a follow up to Sulimon Sattari's comment. In order to accelerate the code substantially, we need to preallocate the temp array in the included dijkstra.m file. To do so replace line 31 through 38 with

temp = zeros(n,1);
for h = 1:n
if ~visited(h) % in the tree;
temp(h) = distance(h);
else
temp(h) = inf;
end
end;

Hope this helps someone!

Mason Song

Excellent

Hari

Thank You for the code. Is it possible to modify this so as to list the k shortest paths between all OD pairs?

shashi bhushan jha

Thank You!

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.

Yuxuan Liang

It cost much time in large matrix, omg

Umer Rasheed

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

Mohammed

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

zhou jianshan

Thank you for your sharing!

mohammed sportman

it is correct (when i run it some problem appear

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.

MATLAB Release Compatibility
Created with R2009a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!