CSCI 3510 Programming Assignment 5

First solution due: June 17, 2:00
Second solution due: June 22 5:00

The Assignment

Write an application that reads a weighted graph, in the same format as for programming assignment 3, followed by two vertices s and t. For example, the input might look like this. 
5
1 2  9
1 3 12
2 4 18
2 3  6
2 5 20
3 5 12
0 0 0
1 5
Your program should print the graph, followed by the shortest path from s to t and the distance from s to t via that path, in a reasonable format. The example input might lead to the following output. 
There are five vertices.
The edges are as follows.

 (1,3) weight 12
 (1,2) weight 9
 (2,5) weight 20
 (2,3) weight 6
 (2,4) weight 18
 (3,5) weight 12

The shortest path from 1 to 5 has length 24 and is
1 -> 3 -> 5

Implementation Hints

Get files graph.cc and graph.h from directory /export/stu/3510 on the Little Rascals (the Sun workstations in Austin 320). Modify that program.

Write your program in a clean way, with reasonably chosen functions. For this assignment, it is not necessary to have more than one module. But a single main program that does everything is unacceptable.

Use Dijkstra's algorithm. Here is a summary of how that algorithm works. s is the start vertex and t is the destination vertex.

Dijkstra's Algorithm

Each vertex holds a current distance and a current next vertex. I will write dist(v) for the distance value of vertex v, and next(v) for the next vertex stored with v.

Each vertex has one of three status values: done, pending or peripheral.

A done vertex v has been finished, and dist(v) is the correct shortest distance from v to s. The shortest path from v to s begins by going to next(v).

A pending vertex v is adjacent (via an edge) to at least one done vertex, but is not done. Value dist(v) is the shortest distance from v to s, provided there is a restriction that the path taken from v to s must begin by going from v to a done vertex. Vertex next(v) is the done vertex to go to from v to get to s. 

       v ------> next(v) -----> ... --------> s
Note that it is possible, for a pending vertex v, that there is a better way to get from v to s that starts by going to a different vertex, one that is not yet marked done.

A peripheral vertex is one that is neither done nor pending. Its dist and next values are meaningless. There is no edge between any done vertex and any peripheral vertex.

The algorithm begins by marking the start vertex s as done and setting its distance to 0. Each vertex v that is adjacent to s is marked pending, with dist(v) set to the weight of the edge between v and s. All other vertices are marked peripheral.

The algorithm then repeatedly does the following basic step, until vertex t is done, or there are no more pending vertices.

  1. Find a pending vertex u where dist(u) is as small as possible.

  2. Mark vertex u done.

  3. Update the status, distance and next edge of every vertex v that is adjacent to u. Those vertices are found by scanning the adjacency list of u. For each such vertex v:

    1. If v is done, then do not update its data.

    2. If v is pending, then it remains pending, but it might be necessary to update dist(v) and next(v). An update is done if the path that goes from v to u and then (possibly by several edges) to s is shorter than the current dist(v) value. For example, suppose that vertex v currently has dist(v) = 12. Suppose that the new done vertex u has dist(u) = 7, and that the edge between u and v has weight 3. Then it is better to go from v to s via u (total distance 3 + 7 = 10) than to take the previous path of distance 12. So you update dist(v) = 10 and next(v) = u.

    3. If v is peripheral, then it must be marked pending. If the edge between u and v has weight w, then dist(v) is set to dist(u) + w, since the best known way to get from v to s is to go from v to u (distance w) and then go from u to s (distance dist(u)). next(v) should be set to u, indicating that the best currently known way to get from v to s starts by going from v to u.

Be sure to make reasonable functions. Do not put all of the parts of Dijstra's algorithm in a single function.

When the algorithm is finished, you will be able to follow a path from t back to s by following the chain of next vertices. 

     t -----> next(t) -------> next(next(t)) ----> ... -----> s
Print that chain out backwards. The easiest way to do that is to use recursion. To print a path backwards, starting at vertex u, print the path starting at next(u) backwards, then print u.