Description
In this lab, you will implement the Dijkstra’s 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.
1 Requirement for the Dijkstra algorithm
Design the first Dijkstra’s 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 Dijkstra’s 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 min−heap f o r the p r i o r i t y queue
}
The effect of the Dijkstra’s 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.
- The graph data structure needs to be expanded to handle the edge weight.
- 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.
- You will also modify the R file to randomly generate large positively weighted graphs.
- 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()
- 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().
- 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.
- 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.
- 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 TestyourimplementationsofDijkstra’salgorithms
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 Dijkstra’s 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:
- Dijkstra_list runtime as a function of number of nodes in the graph, given the number of edges.
- Dijkstra_heap runtime as a function of number of nodes in the graph, given the number of edges.
- Dijkstra_list runtime as a function of number of edges in the graph, given the number of nodes.
- 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 Dijkstra’s 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 Dijkstra’s 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
NM271@+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:
NM271@+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 (lat1,lon1) and (lat2,lon2) 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.
