|08 Apr 2012||dijkstra very simple Dijkstra's algorithm to find the shortest path||David B||
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:
|29 Mar 2012||Dijkstra's Minimum Cost Path Algorithm calculates the shortest (least cost) path along edges of a graph using Dijkstra's Algorithm||David B||
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!