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 Dijkstras algorithm to find the shortest paths from a given source vertex to all other vertices in a graph. An efficient implementation of Dijkstras 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.

This project is an Accreditation Board for Engineering and Technology (ABET) required project as part of the accreditation process for our CS and CSE programs, and is not of my design.

Note: This project must be completed individually. Your implementation must use C/C++ and ultimately your code must run on the Linux machine general.asu.edu.

You must build all dynamic data structures, i.e., the min-priority queue and the adjacency lists, by yourself from scratch. All memory management must be handled using only malloc and free, or new and delete. That is, you may not make use of any external libraries of any type for memory management! You may only use the standard libraries for I/O and string functions (stdio.h, stdlib.h, string.h, and their equivalents in C++). If you are in doubt about what you may use, ask me.

Remember that you must use a version control system as you develop your solution to this project. Your code repository must be private to prevent anyone from plagiarizing your work.

1 Implementation of Dijkstras Algorithm

As already stated, an efficient implementation of Dijkstras algorithm uses adjacency lists to represent the graph, and uses a min-priority queue of vertices, keyed by their current distance. Lets 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 Dijkstras 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 xs key to a new value k, where k is less than or equal to xs 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 Dijkstras 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 Dijkstras Algorithm

As you know, Dijkstras 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.

Dijkstras 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 Dijkstras 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 d⁰, then Decrease-Key(Q,v,d⁰)} 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,v_i) with weight w_i, 1 i k, then for each vertex u, output:

u : (v₁;w₁);(v₂;w₂);;(v_k;w_k)

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

On reading find s t 1, your program runs Dijkstras 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 Dijkstras 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;v₁;v₂;;v_k;t

where the sequence of vertices listed corresponds to the shortest path (s,v₁);(v1,v₂)(v_k,t) computed of length k.

While your program reads in only one graph, it may be asked to compute st shortest paths for many different source-destination pairs s and t. Therefore, during the computation of the st 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 cpp (and corresponding include file main.h),
• the implementation of the min-priority queue using a min-heap in the file cpp (and corresponding include file heap.h),
• the graph functions in the file cpp (and corresponding include file graph.h),
• any utility functions in the file 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.