代写改进的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)
INITIALIZE-SINGLE-SOURCE(G,s)
Q = { s }
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 to implement.
Input
As in the previous assignment, your program should read from standard input a
list of data input files, one per line, and should compute timing for each
one. Data input files will be provided in various sizes for timing comparison.
Information about input files will be provided on Canvas. You’ll be required
to run your program with a specified set of different size data files for the
final analysis.
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 represents Figure 24.6 in the
textbook (p. 659):
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
You can use the sample data above for your initial testing (Fig. 24.6 shows
the results for the first example). All supplied input data will have non-
negative edge weights.
Output
Standard Output
Output should be written as text to standard output. The text should be
formatted as CSV (comma separated values). The first line of the file should
contain the column headings, and should contain exactly this text (followed by
an end-of-line):
“v”,”e”,”Algorithm”,”CPU Seconds”,”File”
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,”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 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 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
Analysis
In addition to submitting your source code, you must write a short analysis of
your results (at most just a few paragraphs, 1-2 pages including graph(s)).
- Discuss how the two different multiply algorithms scale with regard to the size of the input (|V| and |E|), according to your results.
- Include at least one graph in your report showing how the two multiply algorithms behave with regard to input size. The CSV file written by your program can be imported directly into Microsoft Excel or other spreadsheet or graphing program for analysis.
What to submit to Canvas
You should submit:
- All your Java or C++ source code, including copies of the CpuTimer.* files. Don’t include any Eclipse project files, object code, .class files, or data files.
- CSV output file you used for your analysis
- Your analysis, as a Microsoft Word or PDF file
Combine all files into a single .zip file to upload to Canvas.
See the assignment on Canvas for due date.
Grading
There are a total of 100 points for this assignment:
- 30 points for BELLMAN-FORD completely implemented and working correctly
- 35 points for MODIFIED-DIJKSTRA completely implemented and working correctly
- 15 points for timing computed correctly
- 20 points for the analysis (points will be deducted for reports longer than 2 pages!)
Partial credit will be given for incomplete results based on examination of
the output and code. Document code well, and explain how far you got in the
project to increase your chances for partial credit. Working code with
severely deficient comments may lose up to 5 points.
