Dijkstra’s Algorithm，，。
Introduction
In this assignment, you’ll implement two algorithms that we’ve studied in class for finding singlesource 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. You’ll also write a brief analysis of your results.
For this assignment, you may use container data types provided by Java such as ArrayList, PriorityQueue, HashMap, etc., or C++ types such as vector, priority_queue, unordered_map, multimap, etc. You may not use any code not provided by the standard libraries of Java or C++ except CpuTimer. You must write your own implementation of the adjacency list graph representation.
Measuring Execution Time
As in Programming Assignments 1 and 2, you’ll 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 won’t need to copy the input graphs each time.
Use the same CpuTimer code to measure execution time that you used in the previous assignment. Determine how many iterations to use for any given input size (like the calculation of timingIterations in Assignment 1) such that for very small inputs the timing tests will run at least a few thousand iterations.
Modified Dijkstra’s Algorithm
The version of Dijkstra’s 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 and C++ don’t implement this (a 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 Dijkstra’s 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 it’s 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.
MODIFIED-DIJKSTRA(G,w,s)
1
2
3
4
5
6
7
8
9
|
INITIALIZE-SINGLE-SOURCE(G,s)
Q = #123; s #125;
while Q
u = EXTRACT-MIN(Q)
for each vertex v G.Adj[u]
if RELAX(u,v,w)
if ISINQUEUE(Q,v)
REMOVEFROMQUEUE(Q,v)
INSERTINQUEUE(Q,v)
|
The queue can be implemented using the Java PriorityQueue 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.
The C++ priority_queue implementation does not allow for ISINQUEUE or REMOVEFROMQUEUE equivalent methods. The best strategy is probably to use a vector, which allows equivalents of all the required operations, although mostly in O(n) time. You could also use a multimap with priority as the key, but this would be more complex
There should be two lines written to standard output for each input file, one for each algorithm. Each output line should contain values for these 4 columns. The values “v” and “e” are integers (number of vertices and edges, respectively), and the value of “CPU Seconds” is floating point. For the “Algorithm” column, output one of the strings:
- “B” for BELLMAN-FORD
- “D” for MODIFIEDDIJKSTRA
For the “File” column, write the name of the input file, enclosed in 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,quot;Bquot;,0.0003,quot;graph24-6.txtquot;
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 analysis, it will affect the result time).
Graph Distance Output Files
For each input data file, write two corresponding 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 the same 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 distance computed for that vertex. The vertices need not be in the same order as the input (this makes it easier to us