Java代写：COMP2370 Single Source Shortest Path

代写改进的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.