CS 302 Programming Project
Using Dijkstra's Algorithm
Due Thursday April 26, 2007

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 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 one edge. The edges are listed in arbitrary order.
• If an edge is from source vertex x to target y and has weight w, then the name of x is written first, followed by the name of y, followed by w. The names of the vertices are integers in the range 1 to n.
• Each edge should have a list of out neighbors. Each time you read an edge (x,y,w), increment the out neighbor list for the vertex x, by adding the ordered pair (y,w).
• 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.
• Keep the partially processed vertices in a min-heap, implemented as an array. The heap should contain the names of the vertices, but the key is the value.
• At each step, do the following:
  • Delete the minimum vertex from the heap. Call it 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, or if value[x] + w is less than value[y], then updae value[y]. If y was already in the heap, execute bubbleup. Otherwise, insert it into the heap.
• When the heap 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.