Shortest Path - Visual C++ and the STL
This is a discussion of Dijkstra's shortest path algorithm as presented at the website:
http://www.csi.uottawa.ca/~holte/T26/
The algorithm presented at
that website is a modification of Dijkstra's
shortest-path algorithm. The source code
for a MS Visual C++ STL and g++ implementation is linked at the end of this
discussion.
The Problem
: Given a graph of nodes and edges, where the
edges have a cost associated, find the least cost for traversing the graph from
node to node.
General Statement of
the Solution: Construct an
adjacency graph representation of the graph.
Start with an arbitrary node. Consider the path to that node processed.
Find all nodes reachable from the start node and compute the cost to get to
those nodes. Consider the least costly path to a node to be processed. Repeat
until all nodes are processed.
More Specific
Statement of the Solution:
A. Read the graph data into a data
structure.
B. Pick a start node.
C. Put the start node into a priority
queue. This priority queue always
chooses the next node/path based on least cost.
D. While there are entries in the queue,
process the entries. Put processed
entries into a data structure.
E. Process the entries by finding all
nodes and associated cost reachable by each entry in the queue. If these nodes/costs are not in the queue or
if they cost less than the entry already in the queue, place them in the
queue. Node/costs of less cost will
replace old node/costs. New node/costs
will simply be added.
Pseudo Code of the
Solution:
// Declare
data structures for the original node/costs, the priority queue
// and the processed nodes.
nodes, ready,
processed
read_nodes();
initialize_ready();
while(entries_in_ready()){
process_nodes();
}
print_processed_nodes();
Consider the following directed, weighted graph: nine
This graph can be encoded as:
1 3 2.0
2 3 4.0
2 1 1.0
3 1 1.0
3 5 2.0
4 7 0.5
4 8 0.5
5 4 2.5
6 2 1.0
6 7 1.0
6 9 9.0
7 8 0.5
8 9 1.0
9 9 0.0
-1 -1 -1.0
There are 2 problems in this
graph: 1) there are circular references 2) there are unreachable nodes.
In my source code I have
implemented a function that checks for reachability.
This could be run prior to trying to find a minimum cost path between 2 nodes.
Reachability is a simpler problem but follows the same general
method of Dijkstra.
You put the source node onto a stack.
While there are nodes on the stack, pop the top node. Put the popped
node into a done vector. For the popped
node, find all connecting nodes that are not in done and place them onto the
stack. When you encounter the target
node you are done. If you empty the stack and do not encounter the target node,
you have no path. Using the stack you do
a depth first search. Changing the stack
to a que provides a breadth first search.
Let's manually walk through
the Dijkstra algorithm for the weighted graph of 9
nodes:
Place the triple <1,1,0>
into the ready que.
The entries in the triple are node: 1 path to node: 1 and distance to
node: 0. (I used a structure for the triple and implemented the path as a STL
linked list of ints).
There are no entries in the processed data structure. While there are entries in
the priority que, process nodes.
ready processed INITIAL
<1,1,0>
ready processed PROCESS LEAST COST
<1,1,0>
ready processed REACHABLE IN READY
<3,1-3,2> <1,1,0>
ready processed PROCESS LEAST COST
<1,1,0>
<3,1-3,2>
ready processed REACHABLE IN READY
<2,1-3-2,6> <1,1,0>
<5,1-3-5,4> <3,1-3,2>
ready processed PROCESS LEAST COST
<2,1-3-2,6> <1,1,0>
<3,1-3,2>
<5,1-3-5,4>
ready processed REACHABLE IN READY
<2,1-3-2,6> <1,1,0>
<4,1-3-5-4,6.5> <3,1-3,2>
<5,1-3-5,4>
ready processed PROCESS LEAST COST
<4,1-3-5-4,6.5> <1,1,0>
<3,1-3,2>
<5,1-3-5,4>
<2,1-3-2,6>
ready processed REACHABLE IN READY
<4,1-3-5-4,6.5> <1,1,0>
<3,1-3,2>
<5,1-3-5,4>
<2,1-3-2,6>
ready processed PROCESS LEAST COST
<1,1,0>
<3,1-3,2>
<5,1-3-5,4>
<2,1-3-2,6>
<4,1-3-5-4,6.5>
ready processed REACHABLE IN READY
<7,1-3-5-4-7,7> <1,1,0>
<8,1-3-5-4-8,10.5> <3,1-3,2>
<5,1-3-5,4>
<2,1-3-2,6>
<4,1-3-5-4,6.5>
ready processed PROCESS LEAST COST
<8,1-3-5-4-8,10.5> <1,1,0>
<3,1-3,2>
<5,1-3-5,4>
<2,1-3-2,6>
<4,1-3-5-4,6.5>
<7,1-3-5-4-7,7>
ready processed REACHABLE IN READY
<8,1-3-5-4-7-8,7.5> <1,1,0>
(replaced
previous- <3,1-3,2>
because
of less cost) <5,
<2,
<4,1-3-5-4,6.5>
<7,1-3-5-4-7,7>
ready processed PROCESS LEAST COST
<1,1,0>
<3,1-3,2>
<5,
<2,
<4,1-3-5-4,6.5>
<7,1-3-5-4-7,7>
<8,1-3-5-4-7-8,7.5>
ready processed REACHABLE IN READY
<9,1-3-5-4-7-8-9,8.5> <1,1,0>
<3,1-3,2>
<5,
<2,
<4,1-3-5-4,6.5>
<7,1-3-5-4-7,7>
<8,1-3-5-4-7-8,7.5>
ready processed PROCESS LEAST COST
<1,1,0>
<3,1-3,2>
<5,
<2,
<4,1-3-5-4,6.5>
<7,1-3-5-4-7,7>
<8,1-3-5-4-7-8,7.5>
<9,1-3-5-4-7-8-9,8.5>
DONE
Note: The unreachable nodes
were not processed: There was no circular dependency. The minimum cost to each node
reachable from 1 is in processed.
Source Code: graph.zip (greatly cleaned up
from the code I presented in class)
Note: there are 2 example graphs. graph.txt and graph1.txt. To compile and execute the program, unzip and click on graph.dsw. If you have MSVC++ it will open and then you can compile and run. This code compiles in g++ if you just replace #define gpp 0 with #define gpp 1. Try replacing edge 4-8 with a 0.5 cost (instead of the original 4.0 cost). What happens to the minimum cost to get to node 9?