CSC 269 Programming Project
Using Dijkstra's Algorithm
Due Friday August 16, 2002

• If you use "off the shelf" code from any source, please cite the source.
• Write a program that, given a weighted directed graph G and a start vertex s, computes the minimum weight path from s to all vertices reachable from s.
• The input file of your program will be a text file containing any number lines, each line containing one edge of a weighted directed graph. 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 vertices are strings of digits of length 4.
• Read the edges one at a time. Each time you encounter a vertex, insert it into a search structure, or make sure it is already there.
• Each edge should have a list of out neighbors. Each time you read an edge, increment the out neighbor list for the source vertex. The out neighbor list should contain the weights of the edges.
• Each vertex record should have fields to indicate whether the vertex is fully processed or partially processed.
• Keep the partially processed vertices in a heap, implemented as an array. It is helpful for each vertex record to contain the current index of that vertex in the array.