Back in 2000, I posted a Graph Search unit that contained the data structure describing graphs (nodes and edges).  It has "depth first" and "breadth first" search procedures that look for ways to get from some starting node to some goal node.   I recently modified the structure to allow weights  to be associated with the edges which connect nodes.   A new procedure implements "Dijkstra's Shortest Path Search algorithm, a clever and relatively efficient way to search for shortest paths between nodes.   The algorithm finds the shortest paths from a specified start node to any other reachable node (or all reachable nodes) for graphs with positive weights (or costs, or distances) between nodes. 

Edsger Wybe Dijkstra, programmer, professor,  and mathematician,  invented and published his Shortest Path algorithm early in his career, around 1960 as best I can determine.  He died in 2002, but you can find many of his writings and learn more about his somewhat eccentric character by searching on his full name.  I would like to have known him.       

The immediate motivation was problem number 83 in the Euler Project programming challenges at ProjectEuler.net, a great site if you think you are a pretty good programmer.  There are other sections of the site with lots of good math problems that do not require programming skills.     In any event, Problem 83 asks for the shortest path from top left to bottom right of an 80x80 matrix of positive integers.  Moves can be made up, down, left or right which is what makes the problem hard.  The demo program included here does not solve that problem, but could be adapted to do so, if you figure out how to represent the matrix as a graph. 

The demo randomly assigns weights to the same graph used in the 10 node graph in the original Graph Search demo program and calls the Dijkstra search procedure to  find the shortest path.  I have included a "verbose" feature that will let you see algorithm working step by step.   It works so well that I found several ways to improve the program when I  first ran "verbosely".   I think I'll add the same feature to Depth and Breadth first procedures one of these days. 

1. "Closest" unchecked is node 01 with weight to it = 0 2. Node 02 through node 01 has path weight 70 3. *** It is the smallest path so far from start to 02 2. Node 03 through node 01 has path weight 69 3. *** It is the smallest path so far from start to 03 4. All paths from 01 checked 1. "Closest" unchecked is node 03 with weight to it = 69 2. Node 06 through node 03 has path weight 94 3. *** It is the smallest path so far from start to 06 2. Node 07 through node 03 has path weight 70 3. *** It is the smallest path so far from start to 07 2. Node 10 through node 03 has path weight 122 3. *** It is the smallest path so far from start to 10 4. All paths from 03 checked 1. "Closest" unchecked is node 02 with weight to it = 70 2. Node 04 through node 02 has path weight 149 3. *** It is the smallest path so far from start to 04 2. Node 05 through node 02 has path weight 143 3. *** It is the smallest path so far from start to 05 4. All paths from 02 checked 1. "Closest" unchecked is node 07 with weight to it = 70 2. Node 10 through node 07 has path weight 121 3. *** It is the smallest path so far from start to 10 4. All paths from 07 checked 1. "Closest" unchecked is node 06 with weight to it = 94 4. All paths from 06 checked 1. "Closest" unchecked is node 10 with weight to it = 121 5. Destination node 10 found! Shortest Path from 1 to 10: Node: 01 Total distance so far: 0 Node: 03 Total distance so far: 69 Node: 07 Total distance so far: 70 Node: 10 Total distance so far: 121

Find shortest path from "1" to "10"

Dijkstra's Algorithm solution

Addendum October28, 2005:  The source for this program was repackaged today, moving UTGraphSearch, the unit that contains the graph list and search class, to a common DFF library file.  The purpose is to reduce the number of programs to be reposted when a widely used class or routine is fixed or enhanced.  The result is that a one time download of the DFF library file is required if you wish to recompile the program.  

Running/Exploring the Program 

Download source code

Download source code for current DFF library file (DFFLibV13 ).

Download executable