In this assignment, you'll implement two algorithms that we've studied in class for finding single-source shortest paths, the Bellman-Ford and Dijkstra algorithms.

You'll write code to implement these algorithms. You'll measure the performance of these two algorithms on various size graphs, and compare the execution times of the two algorithms as the graph size increases.

For this assignment, you may use container data types provided by Java such as ArrayList, PriorityQueue, HashMap, etc. You may not use any code not provided by the standard libraries of Java except CpuTimer.

As in past assignments, youll run each algorithm multiple times on each input, and measure the average execution time. Since the Initialize-Single-Source resets the results of any previous execution, you wont need to copy the input graphs each time.

Use a cpu timer to measure execution time that you used in the earlier assignments. Determine how many iterations to use for any given input size such that for very small inputs the timing tests will run at least a few thousand iterations.

Modified Dijkstras Algorithm

The version of Dijkstras Algorithm in the book adds all the vertices to the queue Q at the start of the algorithm. However, the optimal time for this algorithm assumes that the queue is a priority queue which can adjust the ordering when a priority changes. The built-in implementations of priority queue in Java dont implement this (one structure that does implement this is called a Fibonacci heap).

We can overcome this difficulty for this assignment by using a less-efficient queue which has some O(n) properties, while keeping the average size of the queue smaller (in the worst case the queue size may still grow to O(V)). This can be accomplished by initializing Q in Dijkstras algorithm to just the start vertex s. The Relax function is modified to return true if the destination distance changed, false if unchanged. A vertex is added to Q when Relax modifies its distance (removing it first if its already in Q). Note: you may also optionally modify Bellman-Ford to stop execution when no changes to distances have occurred during a complete iteration of the outer loop.

The queue can be implemented using the Java PriorityQueue (Links to an external site.)Links to an external site. class, which has add (InsertInQueue), poll(Extract-Min), contains (IsInQueue), and remove (RemoveFromQueue) methods. Some of the methods run in O(1) or O(lg n) time, but others run in O(n) time.

Input

Data input files are text files containing an adjacency list representation of a graph. A data input file contains one line per vertex. The first vertex in the file is always the start vertex for the algorithms. Vertex names are contiguous strings of non-blank characters. Each line contains the source vertex name, followed by pairs of destination vertex names and floating-point edge weights. Each pair indicates a directed edge from the source vertex to the destination vertex. All items are separated by white space (blanks and/or tabs). Represent the weights in your program as type double.

Here are two examples. The first example:

s t 10 y 5 t x 1 y 2 x z 4 y t 3 x 9 z 2 z x 6 s 7

The second example is a similar graph with non-integer weights:

Hobbiton Lothlorien 100.2 Bree 5.2 Lothlorien Gondor 10.9 Bree 20.7 Gondor Rivendell 40.98 Bree Lothlorien 30.3 Gondor 92.0 Rivendell 23.6 Rivendell Gondor 68 Hobbiton 77.7

Output

Standard Output

Output should be written as text to standard output. The text should be formatted as CSV (comma separated values). There should be two lines written to standard output, one for each algorithm. Each output line should contain values for these 5 columns, separated by commas:

Number of vertices (integer)

Number of edges (integer)

Algorithm: the string "B" (with quotes) for Bellman-Ford, "D" for Modified Dijkstra.

The average number of CPU seconds used by each execution of the algorithm (floating point). Cast this value to float before output to make it more readable.

The file name of the input file, with double quotes

For example, an output line might look like this for the first example input above (CPU Seconds is a made-up value):

5,10,"B",0.0003,"graph24-6.txt"

No other lines may be written to standard output. Use standard error for other messages you want to write (and don't write any output while you're collecting CPU times for your final run, it will affect the result time).

Graph Distance Output Files

Write two output files. The name of each file must be the name of the input file with ".bout" appended to the name for the Bellman-Ford output, and ".dout" appended to the name for the Dijkstra algorithm output. For example, for input file "graph24-6.txt", you would write an output file named "graph24-6.txt.bout", and another named "graph24-6.txt.dout". If your program is working correctly, the two output files should have equivalent contents. Each output file should contain one line per vertex, with the vertex name, followed by one or more spaces or tabs, followed by the (floating point) distance computed for that vertex. Cast the distance value to float just before output to make it more readable (we don't need 14+ significant digits). The vertices need not be in the same order as the input (this makes it easier to use a Hashmap/unordered_map to contain the vertices). For example, for the second sample input, an output file might look like this (output shown is correct):

Rivendell 28.8 Gondor 46.4 Hobbiton 0.0 Lothlorien 35.5 Bree 5.2