First solution due: Apr 14, 11:59pm
Second solution due: Apr 23, 11:59pm
A graph has points called vertices and lines called edges connecting the points. Each edge connects one vertex to one other vertex. Two vertices are said to be adjacent if there is an edge that connects them. The following shows a graph in which vertices 1 and 2 are adjacent, but 1 and 4 are not adjacent.
A weighted graph is a graph in which a number called a weight is attached to each edge. The following is an example of a weighted graph.
Think of the vertices as towns and the edges as roads. The weight of an edge is the length of the road.
One thing that you might like to know is how to get from one town to another by the shortest possible route. For example, in the weighted graph above, the shortest route from vertex 1 to vertex 5 is to go from 1 to 3 and then from 3 to 5. The length of that route is 27. You add the weights of the edges that you use.
Write an application that reads a weighted graph from the
standard input, in the
same format as for programming assignment 2, 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
The input says that there are five vertices. There is an edge from
vertex 1 to vertex 2, with weight 9.0, etc. The start vertex s
is 1, and the end vertex t is 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 on the standard output. Follow the form of the
output below.
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
To make it easy to test this program, please make the last two lines of your output have the form shown, where the last line shows the path from s to t, with -> between vertices, and the line before that has the form shown.
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.
Remark. The pointer returned by the getEdges function is marked constant. You will need to use a constant pointer to refer to it. For example, if g is a graph, you can write
const EdgeCell* p = g.getEdges(v);You are allowed to change p, making it point to a different EdgeCell, but you cannot change the EdgeCell itself.
Use Dijkstra's algorithm to compute shortest paths. It works as follows.
Use the Graph class in graph.cpp. It creates an array holding the following information for each vertex.
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.
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. You would write g.getDistance(v). You will rarely find that an algorithm is described in exactly the terms that you will use for a particular implementation of that algorithm.
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. You will write g.getNext(v).
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 (or adjacent 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 the start, s. That is, the shortest path from v to 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 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 to s 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.
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.
After initializing, the algorithm repeatedly performs phases, until vertex t (the target vertex) is done, or there are no more pending vertices. Each phase works as follows.
One phase |
---|
|
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, so that it goes from s to t instead of from t to s. 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.
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.
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.
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(v,p): Remove the value from the queue that has the lowest priority value, and set variable v to that value, and p to its priority. The parameters of remove must be reference parameters. Logically, they are out-parameters. If the queue is empty, q.remove(v,p) should set v = 0 and p = 0.
q.update(v,p): Replace the priority of value v in the queue by p.
q.isEmpty(): Return true if q is empty.
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. To find the pending vertex with the smallest distance, use the remove function to get it from the priority queue.
Use a heap data structure to implement the priority queue class. Heaps were described in class, and are described in the text in Chapter 11.
Add a location array so that location[v] tells the index where v is stored in the heap array. Set location[v] = -1 if v is not in the heap array.
Be sure to keep the location up to date when you perform operations on the heap. Use a function for swapping values in the heap that also makes a corresponding change to the location array. Do not write the swap function blindly, and just hope that it works. Try your swap function by hand. Does it work?
No operation on the priority queue should require looking at every value in the queue. The operations must be efficient. In particular, if there are n things in the priority queue, then a remove, insert or update operation must take time proportional to log2(n). That will not be true if you scan the entire array.
Please use the following file names.
Keep your functions short and simple. Do not write long function definitions.
Provide a clear, correct and concise contract with every function. The contract must say what the function does, not how it works.
Design your program to read the graph from the standard input and to write to the standard output. For example, to read the graph, use
g.ReadGraph(cin);and to print the graph, use
g.PrintGraph(cout);