CSE310-Project 3 Solved

Problems on graphs are pervasive in computer science, and algorithms for working with them are fundamental. Hundreds of interesting computational problems are expressed in terms of graphs. This project examines the problem of how to compute shortest paths between vertices when each edge has an associated length or weight. Specifically, you will implement Dijkstra’s algorithm to find the shortest paths from a given source vertex to all other vertices in a graph. An efficient implementation of Dijkstra’s algorithm uses adjacency lists to represent the graph, and uses a min-priority queue of vertices, keyed by their current distance. This requires the implementation of a min-priority queue using a min-heap.

1         Implementation of Dijkstra’s Algorithm
As already stated, an efficient implementation of Dijkstra’s algorithm uses adjacency lists to represent the graph, and uses a min-priority queue of vertices, keyed by their current distance. Let’s recall the definition of a min-priority queue.

1.1        Min-Priority Queue
A priority queue is a data structure for maintaining a set S of elements, each with an associated value called a key. Priority queues come in two forms: Max-priority queues and min-priority queues. Our focus is on a min-priority queue because Dijkstra’s algorithm finds the shortest path to each vertex from a source, i.e., it works to minimize the path length.

A min-priority queue supports four operations:

1.   Insert(S,x): Inserts the element x into the set S, which is equivalent to the operation S = S ∪{x}.

2.   Minimum(S): Returns the element of S with the smallest key.

3.   Extract-Min(S): Removes and returns the element of S with the smallest key.

4.   Decrease-Key(S,x,k): Decreases the value of element x’s key to a new value k, where k is less than or equal to x’s current key value.

Not surprisingly, we can use a min-heap to implement a min-priority queue. In a given application, elements of a priority queue correspond to objects in the application. For Dijkstra’s algorithm, an element of a min-priority queue has three fields, corresponding to a vertex v, the predecessor of v, and the current known minimum distance to v. You are to build the priority queue keyed on the distance field of an element.

In this project, you must implement the functions of the min-priority queue using a min-heap. You should be able to adapt the functions of a max-heap discussed in class to implement a min-heap, and from them, the min-priority queue functions.

1.2        Dijkstra’s Algorithm
As you know, Dijkstra’s algorithm solves the single-source shortest-paths problem on a weighted, directed graph G = (V,E) for the case in which all edge weights are non-negative. Therefore, we assume w(u,v) ≥ 0 for each directed edge (u,v) ∈ E.

Dijkstra’s algorithm maintains a set S of vertices whose final shortest-path weights from the source s have already been determined. The algorithm repeatedly selects the vertex u ∈ V − S with the minimum shortest-path estimate, adds u to S, and relaxes all edges leaving u.

You are to implement Dijkstra’s algorithm using the psuedocode that follows, using a min-priority queue Q of vertices keyed by their distance values, and an adjacency list representation for G. The functions Initialize-Single-Source and Relax were provided and discussed in class.

 

Algorithm 1 Dijkstra(G,w,s)

 

Initialize-Single-Source(G,s) {Initialize distance and predecessor of each vertex v ∈ V }

S = ∅ {S is initially empty because no shortest-paths are determined yet}

Q = V {Use Insert(Q,v) to insert each vertex v ∈ V into the min-priority queue Q} while ( Q 6= ∅ ) do

u = Extract-Min(Q) {Extract the vertex u with current minimum distance from Q} S = S ∪{u} {Add u into the set S of vertices whose final shortest-path has been determined} for each vertex v adjacent to u do

Relax(u,v,w) {If the distance to v decreases to d0, then Decrease-Key(Q,v,d0)} end for

end while

 

You are responsible for defining the structure (i.e., struct) for the elements in the min-heap (and hence the min-priority queue), and the structure for the adjacency list representation of the graph. Be sure to place your definitions in appropriately named include files as described in §1.4.

1.3        Input and Output Format
First, your program is to read in a graph from stdin and construct its adjacency list representation. Recall that the adjacency list representation of a graph is an array (indexed by vertex), where the list for vertex v corresponds to a singly linked list of outgoing neighbours of v (the list of neighbours need not be ordered; you should be able to repurpose some of the you code for the hash table in Project 2).

In order to read the graph, the first line of input contains two integers n and m, which correspond to the number of vertices and the number of edges of the graph, respectively. This line is followed by m lines, where each line contains three integers: u, v, and w. These three integers indicate the information associated with an edge, i.e., that there is a directed edge from u to v with weight w. Note that the vertices of the graph are indexed from 1 to n (and not from 0 to n − 1).

Following the input describing the graph, your program now processes commands, one per line. There are three commands:

•    stop. On reading stop, your program must exit gracefully, with a return code of zero. Recall that, by convention, a return value of zero signals that all is well; non-zero values signal abnormal situations.

•    write. On reading write, your program must write the graph to stdout. The output format of the write command is as follows: The first line should contain two integers, n and m, where n is the number of vertices and m is the number of edges in the graph, respectively. This line must be followed by n lines, one for each vertex. If vertex u has k neighbours (u,vi) with weight wi, 1 ≤ i ≤ k, then for each vertex u, output:

u : (v1;w1);(v2;w2);...;(vk;wk)

• find s t flag, where flag is either zero or one.

On reading find s t 1, your program runs Dijkstra’s shortest path algorithm to compute the shortest path from s to t, and prints out the length of this shortest path to stdout. The information output format is:

LENGTH:` where ` is the shortest path length.

On reading find s t 0, your program runs Dijkstra’s shortest path algorithm to compute a shortest path from s to t, and prints the actual path (sequence of vertices) to stdout. The information output format is:

PATH:s;v1;v2;...;vk;t

where the sequence of vertices listed corresponds to the shortest path (s,v1);(v1,v2)...(vk,t) computed of length k.

While your program reads in only one graph, it may be asked to compute s-t shortest paths for many different source-destination pairs s and t. Therefore, during the computation of the s-t shortest path, your program must not modify the given graph.

1.4        Modular Design
You should use modular design for this project. At the minimum, you must have:

•    the main program in the file main.cpp (and corresponding include file main.h),

•    the implementation of the min-priority queue using a min-heap in the file heap.cpp (and corresponding include file heap.h),

•    the graph functions in the file graph.cpp (and corresponding include file graph.h),

•    any utility functions in the file util.cpp (and corresponding include file util.h),

•    a makefile named makefile that compiles and links the individual executables into a single executable named dijkstra, when the command make dijkstra is executed.