Homework 7

Out: Thu 20 November 1997
Due: Thu 4 December 1997

Programming Assignment

Write a program using Dijkstra's algorithm (discussed in class) to compute the shortest paths in a graph. Use an array implementation of a heap. (At first, just use a linear scan of all the vertices for the smallest value vertex to add. Then, once this is working, convert to a heap.)

Take input from the file input.dat, which will be of the format:

1. The first line contains a single integer, the number of vertices in the graph. If this number is n, the vertices are named 0 through n-1.
2. Each succeeding line is one edge, containing a triple of integers a b c where the edge connects vertex a to vertex b and has weight c.

A sample input file is exampleSP1.txt.

Algorithm Summary:

As discussed in class, the algorithm works by partitionning vertex set V into V1, the set of processed vertices, and V2, the set of unprocessed vertices. At first, all of V is in V2. Taking one vertex v from V2, put it in V1 and update the value of all of the neighbors of v which are in V2.

To update a vertex w in V2, which is a neighbor of v, consider if the path from the root of the tree to w is better if it goes through v. Currently, the value of w is the length of the best path (with smallest length) to w. If the value of v plus the weight of edge v, w is less than that, update the value of w to this sum, and set the parent of v to w.

At each cycle of the algorithm. Choose the vertex from V2 of minumum value and move it into V1, updating neighbors as described. Begin with V1 empty, all vertices in V2, the root having value 0, and all other vertices having value infinity. End when V2 is empty.

Submitting Homework:

Call your program ShortestPath.C, and use the command

   PostIt ShortestPath.C