First solution due: Wed. April 4
Second solution due: April 20.
5 1 2 9 1 3 12 2 4 18 2 3 6 2 5 20 3 5 12 0 0 0 1 5Your 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
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.
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)) ----> ... -----> sPrint 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.
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.