CSCI 3510
Summer 2003
Programming assignment 4

First solution due: Thursday, July 24
Second solution due: Tuesday, July 29

The assignment

Write an application that reads a weighted graph from the standard input, in the same format as for programming assignment 3, followed by two vertices s and t. (But for this assignment, the edge weights are real numbers.) For example, the input might look like this. 

5
1 2  9.0
1 3 12.0
2 4 18.0
2 3  6.0
2 5 20.0
3 5 12.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, on the standard output. The example input might lead to the following output. 
There are 5 vertices.
The edges are as follows.

 (1,3) weight 12.000
 (1,2) weight 9.000
 (2,5) weight 20.000
 (2,3) weight 6.000
 (2,4) weight 18.000
 (3,5) weight 12.000

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

A starting point

I have decided to have some mercy on you and give you a starting point. You can use the following abstract data type for your graphs. It will save you some work. Just add this ADT implementation to your program. Please do not use this abstract data type for program 3. That should be a separate work.

Dijkstra's algorithm

Use Dijkstra's algorithm to compute shortest paths. It works as follows.

Information that the algorithm keeps as it runs

Create an array holding, for each vertex

  1. A status value (one of done, pending or peripheral). A vertex with status done is called a done vertex, a vertex with status pending is called a pending vertex, and a vertex with status peripheral is called a peripheral vertex. See the definition of type StatusType in the file graph.h that has been provided.

  2. A current distance from the start vertex. For convenience I will write dist(v) in this assignment for the current distance value stored for vertex v. Do not presume that this is C++ notation.

  3. A current next-vertex. This is the vertex to go to on the way to the start. For convenience I will write next(v) for the current next-vertex stored with vertex v. Again, this is not intended to be the way you will write this in your C++ program.

  4. A linked list of edge descriptions, where each edge consists of another vertex and a weight. These are the edges that are connected to this vertex, and this list is called the adjacency list of this vertex.

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 the start vertex s begins by going to next(v). It continues to vertex next(next(v)), then to next(next(next(v))), etc. until it reaches s.

A pending vertex v is adjacent (via an edge) to at least one done vertex, but is not done. When v is pending, 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. (There might be shorter paths that begin with an edge from v to a vertex that is not yet done.) When v is pending, the currently best known way to get from v to s is to start by going to next(v), and continuing by the shortest path from there.

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

Starting up

The algorithm begins by marking the start vertex s as done and setting dist(s) 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, and next(v) set to s. All other vertices are marked peripheral.

The main computation

After initializing, the algorithm repeatedly performs phases, until vertex t (the target vertex) is done, or there are no more pending vertices. One phase works as follows.

  1. Find a pending vertex u such that dist(u) is as small as possible. See the priority queue, below, for how to do this. If there is no pending vertex, then the algorithm is finished.

  2. Set the status of vertex u to done.

  3. Update the status, distance and next vertex of every vertex v that is adjacent to u. Those vertices are found by scanning the adjacency list of u. The following cases tell how to update the information for a vertex v that is adjacent to u, according to the status of v.

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

    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 from u to s is shorter than dist(v). For example, suppose dist(v) is currently 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 set dist(v) 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)). Set next(v) = u, indicating that the best currently known way to get from v to s starts by going from v to u.

Getting the final answer

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 -----%gt; 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. Of course, in the special case where u is the start vertex s, just print s.

Priority queues

A priority queue (according to the definition used here) is an abstract data type that supports the following operations. I am presuming that it is implemented as a class. You should implement it that way.

  1. An ordinary queue is first-in-first-out. A priority queue instead assigns priorities to the things in the queue. The next one to be removed will be the one with the lowest priority number. You can think of a priority queue as a list of (pri,val) pairs, where val is something that is in the queue and pri is its priority. Your queue can assume that the priorities are real numbers and the values are integers in some small range, from 1 to n. It is allowed for two priorities to be equal, but it is not allowed to have the same value in the queue more than once.

  2. There must be a constructor that takes a parameter n and makes the priority queue so that it can handle values from 1 to n.

  3. q.insert(v,p): Insert a value v with priority p. Here, v has type int and p has type double.

  4. q.remove(): Remove the value from the queue that has the lowest priority value, and return that value. The returned value has type int. (You return the value, not the priority.) If the queue is empty, q.remove() should return -1.

  5. q.update(v,p): Replace the priority of value v in the queue by p.

  6. q.isEmpty(): Return true if q is empty.

  7. q.isFull(): Return true if q is full, and cannot have anything more put into it until something is removed.

You can use a priority queue to keep track of the pending vertices. When a vertex is marked pending for the first time, insert it into the queue, with its current distance being its priority. When the distance of a pending vertex is updated, also update it in the queue, by calling the update function. To find the pending vertex with the smallest distance, use the remove function to get it from the priority queue.

Implement a priority queue and use it in your solution to Dijkstra's algorithm. Think about how to implement it. Your priority queue implementation must be a class, and must be in a separate module.