Search

 
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.

Shortest 2 to 10 path
213710 
March 3, 2016: The original demo calculated the shortest
path from Node 1 to node 10 using random weights (distances) from node to node.
The search was one way but a programmer recently modified the program to search
from node 2 to node 10 and reported a bug when the shortest path happened
to be 213710 which required traveling backwards through node 1. Version
2.0 posted today incorporates twoway searching and allows users to specify
both the start node and the goal node.
Running/Exploring the Program
