代写改进的Dijkstras Algorithm，在指定的时间内，完成路径的快速搜索和寻找。

Introduction

In this assignment, youll implement two algorithms that weve studied in class for finding singlesource shortest paths, the Bellman-Ford and Dijkstra algorithms.

Youll write code to implement these algorithms. Youll 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. Youll 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, 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 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 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 and C++ dont 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 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.

MODIFIED-DIJKSTRA(G,w,s)

1
2
3
4
5
6
7
8
9

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. Youll 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 5t  x 1  y 2x  z 4y  t 3  x 9  z 2z  x 6  s 7

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

Hobbiton    Lothlorien 100.2  Bree 5.2Lothlorien  Gondor 10.9       Bree 20.7Gondor      Rivendell 40.98Bree        Lothlorien 30.3   Gondor 92.0    Rivendell 23.6Rivendell   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 dont write any output while youre 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.8Gondor 46.4Hobbiton 0.0Lothlorien 35.5Bree 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. Dont 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.