Rank: 5872 based on 12 downloads (last 30 days) and 1 file submitted
photo

David B

E-mail

Personal Profile:

 

Watch this Author's files

 

Files Posted by David B
Updated   File Tags Downloads
(last 30 days)
Comments Rating
09 Apr 2012 Modified Dijsktra's Algorithm to return all paths that tie for shortest A modification of code published by Jorge Barrera to return all paths that tie for shortest path. Author: David B dijkstra, dijkstras algorithm, shortest path, networks 12 0
Comments and Ratings by David B View all
Updated File Comments Rating
08 Apr 2012 dijkstra very simple Dijkstra's algorithm to find the shortest path Author: Jorge Barrera

This is great code. As others have pointed out, it could be commented better, but having said that, it's the easiest implementation of Dijkstra's Algorithm to understand that is available on the file exchange. As a beginner programmer, I appreciate the simplicity.

The previous commenter pointed out, matriz-costo is an n x n adjacency matrix. To elaborate, elements reflect the cost of traveling between corresponding nodes. Any element set to zero implies a cost-free path exists between those two nodes. I usually set the elements corresponding to non-adjacent nodes to an arbitrarily large number (it might also work to set them to inf -- I haven't tried it).

My one wish is that the output included multiple paths if there is a tie for which path is shortest. I modified the code to return ties. It is posted here:

http://www.mathworks.com/matlabcentral/fileexchange/36086

Thank you!!

29 Mar 2012 Advanced Dijkstra's Minimum Path Algorithm calculates the shortest (least cost) path along edges of a graph using Dijkstra's Algorithm Author: Joseph Kirk

The function works great except when two or more paths whose start and end nodes are the same are tied for shortest path. Then the function only returns one of the paths as shortest path. I am attempting to fix this, but I'm a beginner programmer, and its difficult for me to follow the steps in the algorithm. If you could fix this so that all paths whose length is equal to the shortest path length for a given start/end node are recorded, that would be wonderful and much appreciated!

Contact us