In this lab, you will implement the Dijkstras algorithm. You will use two types of data structure to construct a priority queue to be used in the algorithm: a linked list and a minheap. You will test your implementation and also compare the performance of the two data structures on large graphs.

You have an opportunity to earn 300% extra credit by writing a map routing program that will find a route from an origin to a destination using a world travel map.

1 Requirement for the Dijkstra algorithm

Design the first Dijkstras algorithm with the following function prototype that uses an unsorted linked list as priority queue:

void D i j k s t r a _ l i s t ( Graph & G, Node & s )

{

/ /	Input : graph G, e i t h e r undirected or	directed , and
/ /	a source node s
/ /	Output : the e f f e c t of the algorithm	i s that a l l nodes
/ /	are marked with a distance from s
/ /	Perform D i j k s t r a s algorithm on the	input graph from
/ /	a given node s
/ /	Use an unsorted linked l i s t f o r the	p r i o r i t y queue

}

Design the second Dijkstras algorithm with the following function prototype that uses a minheap as priority queue:

void Dijkstra_heap ( Graph & G, Node & s )

{

/ / Input : graph G, e i t h e r undirected or directed , and / / a source node s

/ / Output : the e f f e c t of the algorithm i s that a l l nodes / / are marked with a distance from s

/ / Perform D i j k s t r a s algorithm on the input graph from

/ / a given node s

/ / Use a minheap f o r the p r i o r i t y queue

}

The effect of the Dijkstras algorithm on the graph G is distance labels indicating the distance from source node s to every node in the graph. They will be stored within the Graph data structure. You can enhance the graph class from previous labs in more than one way. You are free to design your strategy and describe it in your lab report. The distance values must not be saved as global variables.

2 Technical notes

The priority queue is a dynamically changing data structure and its implementation can be subject to memory problems.

1. The graph data structure needs to be expanded to handle the edge weight.
2. The graph file will contain three numbers in a row, where the last number is the weight of the edge defined by the first two nodes. Your code for reading/writing a graph file will need to be updated to handle the weight as well.
3. You will also modify the R file to randomly generate large positively weighted graphs.
4. When using an unsorted linked list for the priority queue, the removemin operation can be achieved by finding the minimum element and then removing it from the list. To traverse a list, you cannot use an index but you can use an iterator. To remove an element from a list, you can use the list::erase()
5. The C++ function make_heap() by default makes a maxheap, not minheap. You can make a minheap by specifying a customized comparison function optional to make_heap().
6. Your code must determine the position of a node in the heap in constant time before calling the decreasekey operation on the heap. You can maintain a heap index for each node to resolve this issue.
7. As the removemin and decreasekey operations will modify the heap, the positions of each node in the heap must be updated accordingly. You can manage the positions of each node in the heap via the heap index.
8. You can use the following C++ function

numeric_limits<double>::infinity()

to define infinity for the initial distance of each node other than s. The header file limits must be included to use this function. This option is preferable to either 1 or a very large number from the software engineering point of view.

3 TestyourimplementationsofDijkstrasalgorithms

Generate five examples of weighted graphs to test your code. The graphs do not have to be very large but must represent a variety: cyclic/acyclic, directed/undirected, and some having more than one connected component.

Your C++ program must include a main() function that calls the testall() function. When the program is compiled by a C++ compiler it generates a binary executable file that will run when invoked from the command line.

4 Plot the runtimes of the two Dijkstras implementations

After testing the correctness of the the program, you will study how the runtime scales with the size of graph for the two methods. Use the random graph function you developed in Lab 4 to generate random graphs of increasing sizes.

You will produce four curves in R:

1. Dijkstra_list runtime as a function of number of nodes in the graph, given the number of edges.
2. Dijkstra_heap runtime as a function of number of nodes in the graph, given the number of edges.
3. Dijkstra_list runtime as a function of number of edges in the graph, given the number of nodes.
4. Dijkstra_heap runtime as a function of number of edges in the graph, given the number of edges.

Ideally, the first two curves should be plotted in the same figure for easy comparison and the last two in another figure.

Your algorithm must be able to handle graphs with 10,000 or more nodes and 1,000,000 or more edges in the order of tens of seconds.

5 Extra credit (300%): Shortest routes between any two waypoints on earth

You will apply the Dijkstras algorithm on a world travel map [Teresco, 2012] (http: //courses.teresco.org/metal/) to find a shortest path from one place to another. The map contains 587,376 highway waypoints (nodes) and 665,270 road segments (edges) connecting them on the Earth.

5.1 Travel Mapping Graph file format

The map we will use is in a Travel Mapping Graph (tmg) simple format as described in http://courses.teresco.org/metal/graphformats.shtml:

• The first line specifies the file format. It consists of three spaceseparated entries, the first of which must be TMG. The second is a version number, which much be 1.0. The third entry is either simple or collapsed indicating whether the edge data is in simple format or collapsed edge format.
• The second line consists of two numbers: the number of vertices (waypoints) |V |, and the number of edges, |E|, (road segments that connect adjacent waypoints).
• The next |V | lines describe the waypoints. Each line consists of a string describing a waypoint, followed by its latitude and longitude as floatingpoint numbers.
• The last |E| lines describe the road segments. Each line consists of two numbers specifying the waypoint numbers (0based and in the order read in from this file) connected by this road segment, followed by a string with the name of the road or roads that form this segment. For collapsed format graphs, a line describing an edge can optionally have a list of the spaceseparated latitudes and longitudes of shaping points that define a more accurate path (for both mapping and for computing distances) of the road segment.
• A simple format graph is simply a collapsed format graph with no edge shaping points.

You will download the file tm-master-simple.tmg from http://travelmapping.net/graphdata/tm-master-simple.tmg The file size is about 33.3 MB.

Please note that the graph should be treated as undirected.

5.2 The routing task

You will use the Dijkstras algorithm you have just developed to find the shortest path from a given original waypoint to a destination waypoint. For example, if the input pair of waypoints is

[email protected]+X478507 35.807616 104.446678

and

NY11C_N/US11_N 44.776047 74.672871

you should print out a shortest path from the first waypoint (in New Mexico) to the second (in update New York) in the following fashion:

Origin:

[email protected]+X478507 35.807616 -104.446678

[road segment 1]

[intermediate waypoint 1]

[road segment 2]

[intermediate waypoint 2] [road segment 3]

Destination:

NY11C_N/US11_N 44.776047 -74.672871 Total distance: 2021 miles

If the two waypoints are on roaddisconnected continents (e.g., one in Asia one in North America), your program should report that no road is possible to connect the two waypoints.

5.3 The distance between two waypoints

In order to compute the total distance, your code will use the latitude and longitude of each pair of waypoints (lat₁,lon₁) and (lat₂,lon₂) to estimate edge length in miles using the Haversine formula:

(1)

(2)

/2) (3)

(4)

(5)

where 3961 is the radius of the Earth in miles.