| Assigned: | Monday, October 26 |
| Due: | Monday, November 9, 11:59pm |
This assignment uses weighted graphs, as described in assignment 4. Please be sure that you are familiar with weighted graphs.
Two vertices are said to be adjacent if there is an edge that connects them directly to one another. A given edge is incident on each of the vertices that it connects.
Think of the vertices of a weighted graph 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 following weighted graph, the shortest route from vertex 1 to vertex 5 is to go from 1 to 3 and then from 3 to 5, and the length of that route is 27. You add the weights of the edges that you use.
For this assignment, the weights are real numbers (type double). All of the weights are nonnegative. Edges of weight 0 are allowed.
This assignment uses a different graph representation from assignment 4. Here, we use the adjacency list representation.
A graph should be stored as a structure. It keeps information not only about a graph but related to finding shortest paths in the graph. Put the number of vertices and the number of edges in the structure. Also include an array vertices of VertexInfo structures, where g.vertices[i] gives information about vertex i in graph g. A VertexInfo structure should contain the following information. Imagine we are looking at the structure g.vertices[i] and let s be the start vertex (part of the input).
An adjacency list telling all of the edges that are incident on vertex i. This is a linked list. Each cell in the linked list holds another vertex number j and a weight w, indicating that there is an edge from i to j of weight w.
Note. an edge between u and v is incident on both u and v. So it needs to go into both adjacency lists. Each time your program reads about an edge, it should insert it into two different adjacency lists.
A field distance that is used for finding shortest paths. It is −1 if the distance between s and vertex i is not currently known, and is the distance from the start vertex to vertex i after that distance is known.
A field previous that is used for finding shortest paths. It is the number of the vertex that comes just before i in the shortest path from s to i. If the distance is negative, then previous is meaningless.
Write a program that reads information about a weighted graph from the standard input. The input format is described in detail below. After the description of the graph, the input has two vertex numbers, s and t.
Your program should print a description of 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.
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 15.0
0
1 5
That says that there are five vertices. There is an edge from
vertex 1 to vertex 2 with weight 9.0, an edge from vertex 1 to vertex 3
with weight 12.0, etc. The start vertex s
is 1, and the end vertex t is 5.
The output for this input would be as follows.
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 15.000
The shortest path from 1 to 5 has length 27.000 and is
1 -> 3 -> 5
Create a directory to hold assignment 6 and call your program dijkstra.cpp. Start with the standard template. Follow all of the coding standards.
Below is a description of an algorithm, based on Dijkstra's algorithm, for solving this problem. You are required to use that algorithm, and to follow the guidelines for its implementation. It is not acceptable to rely on a different approach to the problem.
Use sensible terminology in your program. If something is a graph, do not call it an edge. If something is an edge, do not call it a vertex. Make variable and type names sensible. Keep functions short and simple.
Call your file that implements Dijkstra's algorithm dijkstra.cpp.
As always, you must follow the coding standards for this course.
Dijkstra's algorithm is a well-known algorithm for computing shortest paths in a graph.
Imagine yourself at the start vertex. You send out a signal from there along each edge, where the signal takes w seconds to traverse an edge of weight w. For example, if the start vertex is vertex 1 and there is an edge between vertices 1 and 2 of weight 5.1, then the signal sent from vertex 1 reaches vertex 2 after 5.1 seconds.
The first time a signal reaches a vertex v, you record the time at which the signal arrived and from which vertex the signal was sent. (The time is really the distance. We are computing distances, but it is easier to understand the algorithm if you think in terms of time. So we use time and distance interchangeably.)
When vertex 2 receives a signal from vertex 1 at time 5.1, it sends a signal out along the edges that are incident on it. For example, if there is an edge from vertex 2 to vertex 3 of weight 2.0, then the signal from vertex 2 to vertex 3 arrives at vertex 3 at time 7.1 (2 seconds after it was sent from vertex 2).
A vertex can receive more than one signal. Only the first signal that it receives is meaningful. The second and subsequent times a signal arrives at a vertex, the signal is ignored.
The algorithm is finished when a signal reaches the end vertex. The time at which the signal arrived at the end vertex is the distance from the start vertex to the end vertex.
Suppose that previous(u) is the number of the vertex from which the first signal reached vertex u. Then path [u, previous(u), previous(previous(u)), ...] is the shortest path from u back to the start vertex.
This program must simulate sending and receiving signals. To do that, it keeps a list of events, where an event holds three pieces of information, (u, v, t), and indicates the arrival of a signal at vertex v at time t, where the signal was sent from vertex u.
The idea is to store the events in increasing order by the times at which they occur. The program repetitively performs the following steps. For brevity, I write previous(v) for g.vertices[v].previous and distance(v) for g.vertices[v].
Get the next event (u, v, t) representing the arrival of a signal from u to v at time t. The next event is the one that occurs next in chronological order. So it is the one with the smallest time. An event is only considered once, so remove this event.
If no signal has yet arrived at vertex v, then do the following.
Record previous(v) = u and distance(v) = t.
For each edge that is incident on vertex v (say, connecting v with vertex x and having weight w), if x has not yet received a signal then we need to send a signal from v to x. Schedule a new event (v, x, t+w) indicating that a signal will arrive at vertex x, coming from vertex v, at a time that is w seconds after time t.
To get going, set the previous of each vertex to −1 to indicate that no signal has yet arrived anywhere. Then create an initial event (0, s, 0.0) that indicates a signal arriving at the start vertex s at time 0.0, coming from a fictitious vertex 0. Then do the discrete event simulation.
When the simulation is finished, you will be able to follow a path
from t back to s.
t -----> previous(t) -------> previous(previous(t)) ----> ... -----> s
Print 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 previous(u) backwards, then print u.
Of course, in the special case where u is the start vertex
s, just print s. Remember to put -> between
vertex numbers.
You should notice that the operations needed for events are exactly the ones supported by a priority queue. The items in the priority queue are events and their priorities are their times.
Create a type Event. Modify the definition of PQItemType in your priority queue module to be
typedef Event* PQItemType;where Event is the type of an event. So that an item is a pointer to an event. Make sure that you allocate events in the heap. When you remove an event from the event queue, delete it when you are finished looking at it.
You will want a file that describes type Event. Call it event.h. It should look as follows.
#ifndef EVENT_H
#define EVENT_H
struct Event
{
…
};
#endif
Note. Your shortest-distance module should only use the things in the priority queue module that it exports. You are not allowed to make use of the fact that a priority queue is represented as a linked list. Stick to the interface. You will be shocked by the number of points that you lose if you violate the interface.
You are required to put trace (or debug) prints in your program that can be turned on and off. If tracing is turned on, trace the following.
The program should look at the command line. If it contains -t, then tracing should be turned on. If not, tracing should be turned off. Use a global variable that holds 0 if there is no tracing and 1 if there is tracing.
Write a separate function that sets the tracing variable by looking at the command line.
The command line is passed to main. Use the following heading for main.
int main(int argc, char** argv)Parameter argc tells how many parts the command line has, and argv[i] is the i-th part (a null-terminated string). For example, if the command is
./dijkstra -tthen argc is 2, argv[0] is "./dijkstra" and argv[2] is "-t".
A Makefile is provided for you. You can use the following commands with it.
To turn in your work, log into the Linux system, change your
directory for the one for assignment 6,
use the following command.
~abrahamsonk/3300/bin/submit 6 pqueue.cpp pqueue.h event.h dijkstra.cpp
After submitting, you should receive confirmation that the
submission was successful. If you do not receive confirmation,
assume that the submission did not work.
Command
~abrahamsonk/3300/bin/submit 6
will show you what you have submitted for
assignment 6.
You can do repeated submissions. New submissions will replace old ones.
Late submissions will be accepted for one day after the due date. If you miss a late submission deadline by a microsecond, your work will not be accepted.