image thumbnail

Modified Dijsktra's Algorithm to return all paths that tie for shortest

version 1.0.0.0 (3.24 KB) by David B
A modification of code published by Jorge Barrera to return all paths that tie for shortest path.

1.2K Downloads

Updated 9 Apr 2012

View License

This code is heavily based on code published by Jorge Barrera, to the point that I have chosen to include his original documentation along with my own. His original code is linked below.

I produced this modification because I found that no implementation of Dijkstra's Algorithm available on Mathworks File Exchange would return multiple paths that tie for shortest. I have debugged this modification using several small networks, and I believe it works, but I have not yet tested it against large networks so I cannot promise that it is entirely bug-free.

In my additional documentation, you will see that I attempted, unsuccessfully, to further modify the code so that costs are computed through probabilistic addition instead of arithmatic addition (e.g. cost of moving along edges e1 and e2 = 1 - (1-coste1)(1-coste2, instead of e1+e2). I'd greatly appreciate any help that you can offer me to modify the code in this manner.

Cite As

David B (2022). Modified Dijsktra's Algorithm to return all paths that tie for shortest (https://www.mathworks.com/matlabcentral/fileexchange/36086-modified-dijsktra-s-algorithm-to-return-all-paths-that-tie-for-shortest), MATLAB Central File Exchange. Retrieved .

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

Inspired by: dijkstra very simple

Community Treasure Hunt

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

Start Hunting!