## Description

In this day and age, whenever people gear up for a road trip, they turn on their

smart phones and open up Google Maps. Under the directions tab, users type in

the name of their starting location followed by the name of their destination. In

seconds, Google Maps assembles a detailed set of directions covering the shortest route

to the destination city. Such computing speeds are achieved through the use of efficient

mapping algorithms. Unfortunately, how it is these algorithms work is not known

by anyone in the general public. Google has decided to keep the implementations

closed-source and prevent curious computer science students such as yourself from

learning about something awesome. Well, rather than fight a legal battle to have the

licensing rights revised, you are going to get back at the behemoth that is Google

Maps by developing your own competing application. Specifically, here in your humble

beginnings, you will implement a single source shortest path algorithm.

Implementation and Bonus

In order to find a single source shortest path, you must implement the version of

Dijkstra’s algorithm described on Ch12 lect2.ppt powerpoint under blackboard. If you

recall, this algorithm runs in O(V

2 +E) time, where V is the number of vertices in the

graph and E is the number of edges. The O(V

2

) component refers to the number of

operations carried out to find every minimum distance vertex extracted from the set

of unvisited vertices at the beginning of each iteration of the while loop. The O(E)

component results from comparing and possibly updating the distances of all vertices

adjacent to the minimum distance vertices. In other words, the for loop within the

while loop runs O(E) operations in total.

If your graph is not too dense (meaning the graph does not contain an overwhelming

number of edges), you may want to consider storing the set of unvisited vertices in a

min heap using distance to the source vertex as a key. This will help you find all the

minimum distance vertices extracted at the beginning of each iteration of the while

loop in O(V lg(V )) time as opposed to O(V

2

) time. Of course, when you now update

the distance of a neighboring vertex in the for loop below, you must also update that

vertex’s position in the min heap. As you already know, bubbling up an element in

a min heap of n elements takes just O(lg(n)) time, but the initial searching for the

element takes O(n) time. In order to avoid the O(n) search, you must implement a

lookup table that returns a vertex’s index in the min heap in O(1) time. If implemented

correctly, the cumulative time complexity of updating the distance values of vertices

in the min heap version of Dijkstra’s would be O(Elg(V )). In other words, using a

lookup table and a min heap, the for loop within the while loop runs in O(Elg(V ))

time as opposed to the O(E) time seen in the version of Dijkstra’s algorithm described

in the previous paragraph. Thus, the total time complexity of this modified Dijkstra’s

1 CS3610

algorithm is O(V lg(V ) + Elg(V )). As said early, it is more advantageous to use the

min heap version if your graph is not overwhelmingly dense.

In this project, the 6 final grade points will be awarded if you successfully implement

the Dijkstra’s algorithm described in lecture. If you successfully implement the min

heap version, you will be awarded the 6 final grade points plus 3 bonus points.

Input

Input is read from the keyboard. The first line of input is the number of test

cases K. Each of the K test cases is written in the following format:

Individual Test Case Format

n

city 1

city 2

.

.

.

city n

d 11 d 12 … d 1n

d 21 d 22 … d 2n

.

.

.

d n1 d n2 … d nn

The first line of each test case is the number of cities n in the graph. The next n lines

are the names of each city. City names consist only of alphabetic characters. Following

the list of n city names is an nxn distance matrix where each distance d ij is an integer

value in the range [0, 10000] representing the distance of the road connecting city i to

city j. A distance d ij = 0 indicates that there does not exist any road connecting

city i to city j. For this project, all roads will be undirected, which means d ij = d ji

for all cities i and j. As a result, every input distance matrix will be symmetric.

Output

For each test case, output a space delimited list of all the city names in the shortest

path connecting city 1 and city n followed by the integer distance of the path. City

names should be listed in order of when they are to be visited starting from city 1

and ending with city n. If city 1 has multiple shortest paths to city n, just output

one of them. Also note that in every test case, there will always be a path connecting

city 1 to city n.

Sample Test Cases

Use input redirection to redirect commands written in a file to the standard input, e.g.

$ ./a.out < input1.dat.

2

Input 1

1

4

Akron

Athens

Columbus

Cleveland

0 1 2 0

1 0 5 6

2 5 0 7

0 6 7 0

Output 1

Akron Athens Cleveland 7

Turn In

Email your source code to yy471014@ohio.edu with the subject “CS3610 Project 5”.

If you have multiple files, package them into a zip file.

Grading

Total: 100 pts.

• 10/100 – Code style, commenting, general readability.

• 05/100 – Compiles.

• 05/100 – Follows provided input and output format.

• 80/100 – Successfully implemented Dijkstra’s algorithm.

• 30/100 – Bonus points for heap implementations.

3