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

Versione 1.0.0.0 (3,24 KB) da David B
A modification of code published by Jorge Barrera to return all paths that tie for shortest path.
1,3K download
Aggiornato 9 apr 2012

Visualizza la licenza

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.

Cita come

David B (2024). 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. Recuperato .

Compatibilità della release di MATLAB
Creato con R2009a
Compatibile con qualsiasi release
Compatibilità della piattaforma
Windows macOS Linux
Riconoscimenti

Ispirato da: dijkstra very simple

Community Treasure Hunt

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

Start Hunting!
Versione Pubblicato Note della release
1.0.0.0