Clues for CS 302 Programming Project: Dijkstra's Algorithm
These are just suggestions.
I would prefer that you not read this page,
and do it your own way.
-
The input file of your program is an encoding of a weighted directed
graph in outneighbor list form. It will be a text file containing any number
lines. The first line is a single integer n, the size of
the weighted directed graph. Each subsequent line contains the
outneighbor list of one vertex. The vertices are listed in arbitrary
order.
-
Each line consists of the ID of the edge, a number from 1 to n,
following by d pairs, where d is the outdegree of that vertex.
The first number of the pair is the ID of the target vertex,
and the second number, always non-negative, is the weight of that edge.
-
Partially processed vertices should be stored in an
updatable priority queue implemented as a heap.
The heap should contain the names of the vertices, but the key is the value.
-
In your program, each vertex record should have fields to indicate:
-
whether the vertex has been visited,
-
the current back pointer of that vertex,
-
value = the current minimum weight of any path from 1 to that vertex,
-
the current index of that vertex in the heap.
-
At each iteration of the main loop, do the following:
-
Delete the minimum vertex from the updatable priority queue. Call it x.
-
Execute the inner loop once for each outneighbor of x.
For each (y,w) in the out-neighbor list of x, do the following:
-
Determine whether y has been visited.
-
If y has not been visited, let value[y] = value[x] + w,
let back[y] = x, and then
execute insert(y,value[y]).
Else, if
value[x] + w < value[y], then let value[y] = value[x] + w,
let back[y] = x, and then
execute update(y,value[y]).
-
When the updatable priority queue is empty,
if n has not been visited, there is no path
from 1 to n. Otherwise, use the back pointers to print out the minimum
weight path from 1 to n.