## Description

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.

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 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.

1 CSE 310/SLN 82170

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 d

0

, 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.

2

• 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.

## 2 Submission Instructions

Submissions are always due before 11:59pm on the deadline date.

1. Due to the Provost’s changes to the Fall 2020 semester, the time frame for this Project #3 was

compressed. As a result, there is insufficient time to have a milestone graded. Nevertheless, I suggest

that you aim to complete the min-heap implementation of the min-priority queue by the milestone

deadline of Thursday, 11/12/2020.

2. The complete project is due on Tuesday, 11/24/2020. See §2.1 for requirements.

It is your responsibility to submit your project well before the time deadline!!! Late projects

are not accepted. Do not expect the clock on your machine to be synchronized with the one on Canvas!

An unlimited number of submissions are allowed. The last submission will be graded.

3 CSE 310/SLN 82170

## 2.1 Requirements for the Full Project Deadline

Using the submission link on Canvas for the full Project #3, a zip1 file named yourFirstName-yourLastName.zip

containing the following:

Design and Implementation (40%):

1. Your zip file must unzip into, as a minimum, the files listed in §1.4 implementing the main program,

the min-priority queue, graph operations, and any utility functions, and their associated include

files. (10%)

2. The makefile named makefile must compile and link the individual executables into a single executable named dijkstra, when the command make dijkstra is executed on general.asu.edu.

If your program does not pass this step, you will receive zero on this project. (10%)

3. Your code must be well documented, i.e., provide sufficient comments for the variables and algorithms. (10%)

4. Reading the graph, and processing of commands. (10%).

## Correctness (60%):

The correctness of your program will be determined by running your dijkstra program on the several

data sets. Specifically, there are 30 test cases posted on Canvas and 30 test cases that are not posted.

1. Your program produces the correct output for a subset of the posted test cases. (30%)

2. Your program produces the correct output for an unposted set of test cases. (30%)

1Do not use any other archiving program except zip.

4