First solution due: Monday, July 23
Second solution due: Friday, July 27 before the final exam.
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 5 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
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.
Use Dijkstra's algorithm to compute shortest paths. It works as follows.
Create an array holding, for each 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 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. 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. 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.
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 current distance and next vertex 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 dist(s) to 0. Each vertex v that is adjacent to s is marked pending, with its distance 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 (the target vertex) is done, or there are no more pending vertices.
Find a pending vertex u such that dist(u) is as small as possible. See the priority queue, below.
Mark vertex u done.
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. For each such vertex v:
If v is done, then do not update its data.
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.
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.
Of course, in the special case where u is the starte vertex
s, just print s.
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.
A priority queue is conceptually a list of (pri,val) pairs, where pri is the priority and val is the associated value. You 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.
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.
q.insert(v,p): Insert a value v with priority p. Here, v has type int and p has type double.
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.
q.update(v,p): Replace the priority of value v in the queue by p.
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. Use a heap to represent the priority queue. Use the heap manipulation functions, such as reheapUp and reheapDown, to manipulate the heap.
You will need to augment the heap with an array to support the update operation. Your priority queue only needs to handle values that are integers in the range from 1 to n. Create an array location, with indices from 1 to n, where location[k] is the current index in the heap where the value k is stored. Be sure to design reheapDown and reheapUp to modify the location array where appropriate. Use the location array to find a value for updating.