Java程序辅导

CS 3114  Data Structures and Algorithms  J5: Dijkstra's Shortest Path Algorithm with Min-heap 
 
Version 5.00 This is a purely individual assignment! 1 
Dijkstra's Shortest Paths Algorithm (SSAD) 
 
This assignment involves implementing a weighted adjacency list representation of a weighted graph, and using it to 
efficiently apply Dijkstra's shortest paths algorithm (single-source, all destinations) to a weighted graph. 
 
 
Design and implementation requirements 
 
The program will read the specification of a weighted digraph from an input file, whose name will be given on the command 
line. 
 
The input file will begin with two lines specifying the number of vertices, V, in the graph, and the start vertex, S.  Each of 
those values will be preceded by a label that ends with a colon character (':').  The next line will be blank.  That is followed 
by a line of column labels, and a line of delimiters.  The remainder of the file will be V lines, each containing a row number 
followed by a delimiter ('|'), and then V integer values for the weights of the edges in the graph[1]. 
 
Weights will be integers in the range 1 to 99.  Missing edges will be designated by the value 0.  Here's a sample: 
 
Number of vertices: 16 
Start vertex:       6 
 
       0    1    2    3    4    5    6    7    8    9   10   11   12   13   14   15 
----------------------------------------------------------------------------------- 
 0 |   0    0   14    0   38    0    0    0    0    0    0    0    0   49    0    0 
 1 |   0    0    0   87    0   40    0    0    0    0    0    0    0    0    0    0 
 2 |   0    0    0    0    0   51    0   87    0    0    0    0    0    0    0    0 
 3 |   0    0    0    0    0    0    0   58    0    0    0    0    0    0    0    0 
 4 |   0    0    2    0    0    0    0    0    0    0    0    0    0    0    0    0 
 5 |   0    0    0    0   74    0    0    0    0    0    0    0    0    0    0    0 
 6 |   6   55    0    0   71   19    0    0    0    0   17   38    0    0    3    0 
 7 |   0    0    0    0    0   14    0    0    0    0    0    0   34    0    0    0 
 8 |   0    0    0    0    0   42    0    0    0    0    0    0    0    0    0   81 
 9 |   0   63    0    0    0   47    0    0    0    0    0    0   97    0    0    0 
10 |   0    0    0    0   65    0    0    0    0    0    0    0    0    0   42    0 
11 |   0   96    0    0    0    0    0    0    0   45    0    0    0    0    0    0 
12 |   0    0    0    0    0    0    0    0   51    0    0    0    0    0    0    0 
13 |   2    0    0    0    0   91   42    0    0    0   82    0    0    0   96    0 
14 |  24    0    0    0    0    0    0    0    0    0   91    0   95    0    0    0 
15 |   0    0    0   68    0   21    0    0    0    0    0    0    0    0    0    0 
 
Your program will construct a weighted adjacency list representation of the specified graph.  Note that this is a formal 
requirement; use of an adjacency matrix representation will result in a substantial deduction, applied after the fact. 
 
Whether the weighted adjacency list is a formal generic is up to you[2]. You may use any classes from the Java library that you 
find useful.  
 
Output will be written to another file, whose name will also be given on the command line.  The output file consists of two 
sections, one displaying information about the given graph and the other displaying the results of running the SSAD 
algorithm. 
 
The graph information display consists of a line of labels and a line of delimiters (see sample below), followed by V lines of 
output displaying the graph information in a format similar to the list-of-neighbors structure.  For each vertex, there will be 
one row of data listing the vertex number, followed by whitespace and a pipe symbol ('|'), followed by a list of neighbor 
records. 
 
A neighbor record consists of a neighbor (vertex) number, followed by a colon character and a space, followed by the weight 
of the corresponding edge: (10: 91). 
 
The graph information display is followed by a blank line, then a line specifying the start vertex, and another blank line. 
 
CS 3114  Data Structures and Algorithms  J5: Dijkstra's Shortest Path Algorithm with Min-heap 
 
Version 5.00 This is a purely individual assignment! 2 
The SSAD results display begins with two lines of labels and a line of delimiters (see sample), followed by V lines showing 
the results for each possible destination vertex (including the source vertex itself), in numerical order. 
 
Each of these lines consists of three sections, the destination vertex number, the length of the shortest path found, and the 
actual path (a sequence of vertex numbers separated by white space).  If a vertex is not reachable from the source vertex, 
display "INF" instead of the length, and nothing for the path. 
 
Here's an output sample that corresponds to the input sample above: 
 
Node  | Successors 
---------------------------------------------------------------------- 
    0 |    2: 14    4: 38   13: 49 
    1 |    3: 87    5: 40 
    2 |    5: 51    7: 87 
    3 |    7: 58 
    4 |    2:  2 
    5 |    4: 74 
    6 |    0:  6    1: 55    4: 71    5: 19   10: 17   11: 38   14:  3 
    7 |    5: 14   12: 34 
    8 |    5: 42   15: 81 
    9 |    1: 63    5: 47   12: 97 
   10 |    4: 65   14: 42 
   11 |    1: 96    9: 45 
   12 |    8: 51 
   13 |    0:  2    5: 91    6: 42   10: 82   14: 96 
   14 |    0: 24   10: 91   12: 95 
   15 |    3: 68    5: 21 
 
Start vertex is: 6 
 
       Total 
Dest | Weight | Path 
---------------------------------------------------------------------- 
   0 |      6 |   0 
   1 |     55 |   1 
   2 |     20 |   0   2 
   3 |    142 |   1   3 
   4 |     44 |   0   4 
   5 |     19 |   5 
   6 |      0 | 
   7 |    107 |   0   2   7 
   8 |    149 |  14  12   8 
   9 |     83 |  11   9 
  10 |     17 |  10 
  11 |     38 |  11 
  12 |     98 |  14  12 
  13 |     55 |   0  13 
  14 |      3 |  14 
  15 |    230 |  14  12   8  15 
 
 
The SSAD function should take an initialized graph object as one of its parameters; there may be additional parameters to this 
function, and its return type is up to you.  The SSAD function should compute a representation of the path lengths and 
shortest paths, but it should not write any of the display to the output file. 
 
A different function should be passed the representation created by the SSAD function, and write results to an output file, 
whose name was specified on the command line. 
 
Since you'll be implementing the complete program, the interfaces of the weighted adjacency list class and the SSAD function 
are up to you.  
 
  
CS 3114  Data Structures and Algorithms  J5: Dijkstra's Shortest Path Algorithm with Min-heap 
 
Version 5.00 This is a purely individual assignment! 3 
Implementing an Efficient Solution 
 
We described Dijkstras SSAD algorithm in terms of updating a table, which we might call a Dijsktra table.  For the graph 
shown above, the Dijkstra table would start off like this[4]: 
 
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ 
|   0 |   1 |   2 |   3 |   4 |   5 |   6 |   7 |   8 |   9 |  10 |  11 |  12 |  13 |  14 |  15 | 
| INF | INF | INF | INF | INF | INF | INF | INF | INF | INF | INF | INF | INF | INF | INF | INF | 
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ 
 
This table could just be an array of objects, perhaps just an array of integer values[3].  That is easy to create. 
 
In the first iteration of Dijkstra's SSAD algorithm, we'd update the distance for the start vertex to 0: 
 
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ 
|   0 |   1 |   2 |   3 |   4 |   5 |   6 |   7 |   8 |   9 |  10 |  11 |  12 |  13 |  14 |  15 | 
| INF | INF | INF | INF | INF | INF |   0 | INF | INF | INF | INF | INF | INF | INF | INF | INF | 
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ 
 
Then, we'd update the distances for the successors of vertex 6, based on the edge weights.  How do you determine the 
successors of vertex 6?  By using the weighted adjacency list you built earlier.  How do you determine the edge weights?  By 
using the weighted adjacency list.  How do you locate a successor in the Dijkstra table?  Simple.  The vertex number is the 
array index for the vertex, so finding a given neighbor is O(1). 
 
For the example graph, the updated table would now look like this: 
 
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ 
|   0 |   1 |   2 |   3 |   4 |   5 |   6 |   7 |   8 |   9 |  10 |  11 |  12 |  13 |  14 |  15 | 
|   6 |  55 | INF | INF |  71 |  19 |   0 | INF | INF | INF |  17 |  38 | INF | INF |   3 | INF | 
+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ 
 
So far, so good.  Now, for the next iteration, we need to find the vertex with smallest distance… we can easily see that will be 
vertex 14, but if we only use the Dijkstra table, we'd have to do a linear search to choose the next vertex, and that will be O(V) 
on average.  Since we'd have to find V – 1 vertices this way, the cost of running Dijkstra's algorithm would be O(V 2). 
 
We could do better.  If we used a min-heap, ordered on the vertex distances, the next vertex to take would always be at the 
root of the min-heap, and it would cost O(1) to find it.  But… then in order to update the distances for the successors of a 
vertex, the min-heap gives us no efficient way to find them. 
 
So, we need to use both a simple array for the Dijkstra table, and a min-heap to keep track of the minimum-distance vertex: 
 
 
 
 
 
      
 
 
 
 
 
 
 
 
 
 
      
 
  
Dijkstra 
table 
minHeap 
Vertex 
data 
objects 
CS 3114  Data Structures and Algorithms  J5: Dijkstra's Shortest Path Algorithm with Min-heap 
 
Version 5.00 This is a purely individual assignment! 4 
Now, we can: 
 
 Use the weighted adjacency list to determine successors and edge weights. 
 Use the Dijkstra table to update distances for successors, with O(1) access cost. 
 Use the min-heap to find the lowest-distance vertex for each iteration of Dijkstra's algorithm[5], with O(log N) cost to 
remove a vertex from the heap. 
 
The pointers in the Dijkstra table are fixed; that is, they don't change after the table is created.  The pointers in the min-heap 
change positions[6] frequently, as the heap adjusts to changes in the vertex distances. 
 
What data is stored in the vertex data objects?  Obviously the current distance for the vertex would go there, since both the 
Dijkstra table and the min-heap need to access that.  There might be other data that would be useful to store there.  It's up to 
you to determine what, if anything, you want to add. 
 
By having the Dijkstra table and the min-heap both point to the same set of vertex data objects, they share them, and each can 
"see" updates made by the other.  This is a common pattern, useful in situations where we have a set of objects whose 
attributes change, and need to access those objects from different perspectives that depend on those attributes. 
 
What about saving the path information for each "solved" vertex?  A path is just a sequence of edges, or vertex numbers, or 
something.  In our case, each path we care about begins at the start vertex.  So a path sounds like a list, of something…[7] 
 
You may any elements of the Java Library that you find useful.  I advise against using the Java PriorityQueue class in 
this project, because you may find it useful to be able to tweak the internal implementation of the min-heap.  You may also 
use code from the Weiss textbook, but I am not enamored of his code for the heap. 
 
 
Testing 
 
Your main class must be called SSAD, must not belong to a package, and that must implement a main() method. 
 
We will compile your program from the command line as follows: 
 
javac *.java 
 
We will invoke your program from the command line as follows: 
 
java SSAD  
 
 
We will post a number of files specifying weighted graphs, and the corresponding SSAD solutions.  In addition, we will post 
the following three tools: 
 
SSADGen.jar An executable jar file that will generate test data (an input file, and an annotated reference 
solution file to be used with the comparison tool).  Run as: 
 
 java -jar SSADgen   
 
LogComparator.jar An executable jar file that will compare an annotated reference solution file to the file 
generated by your solution, and write score information. Run as: 
 
 java -jar LogComparator.jar   
       
 
Run this with no command-line parameters for further instructions. Since the 
LogComparator tool grades by comparing output, it is important to format your output 
exactly as specified above. 
 
CS 3114  Data Structures and Algorithms  J5: Dijkstra's Shortest Path Algorithm with Min-heap 
 
Version 5.00 This is a purely individual assignment! 5 
gradeJ5.sh A bash shell script that will be used to test your submission; see the header comment for 
instructions.  It is important that you use this script to test the file you plan to submit to the 
Curator, since this will detect whether that file will work correctly. 
 
You can use SSADGen to create individual test cases, run your solution on them, and then use the LogComparator to 
check your results.  Be sure to test with a reasonably large number of test cases; some graphs may contain features that other 
graphs do not.   
 
The shell script is provided so you can be sure that you've packaged your solution correctly before submitting it.  The shell 
script runs a sequence of five tests, rather than just one, so it's also useful for trying to detect bugs in your solution.  Failing to 
use the shell script to check the zip file you plan to submit may lead to unpleasant surprises when the actual grading is done 
on the back end.  Submissions that do not work with the shell script will likely receive a score of zero. 
 
 
What to turn in and how 
 
You should document your implementation in accordance with the Programming Standards page on the course website.  It is 
possible that your implementation will be evaluated, by one of the TAs, for documentation and design, as well as for 
correctness of results.  
 
Submit a flat[8] zip file containing all the .java files that make up your solution, to the Curator System.  Submit nothing 
else.   
 
Your submitted solution will be graded as described earlier in this specification, using a test script created by the supplied 
generator, and several different directed graph files created by the generator supplied for this assignment. 
 
Warnings:   
 
The requirement here is for a zip file.  We will not accept files in any other format (e.g., tar files, 7-zip'd files, gzip'd files, 
jar files, rar files, …).  Such submissions will NOT work with the grading infrastructure used on the back end, and will be 
discarded when we run the grading code ourselves. 
 
In addition, your zip file must be structured so that the file SSAD.java must be in the directory where your submission 
is unpacked.  If you created packages in your solution, the correct directory structure must also be created when your 
submission is unpacked. 
 
You will be allowed to submit your solution multiple times, in order to make corrections.  Your score will be determined by 
testing your last submission.  The Curator will not be used to grade your submissions in real time, but you will have already 
done the grading using the posted code. 
 
Instructions, and the appropriate link, for submitting to the Curator are given in the Student Guide at the Curator website:  
 
http://www.cs.vt.edu/curator/. 
 
 
Grading 
 
This assignment will be auto-graded using Java 11 (which may matter) under CentOS (which should not matter at all), and the 
posted testing/grading code.  
 
Your submission will be graded using a collection of several different graphs (created by the SSADGen tool) and the 
LogComparator tool.   
 
In addition, a TA will examine your graded submission to verify that you have implemented and used a weighted adjacency 
list representation of the graph, and a min-heap when choosing the next vertex to "solve". 
 
CS 3114  Data Structures and Algorithms  J5: Dijkstra's Shortest Path Algorithm with Min-heap 
 
Version 5.00 This is a purely individual assignment! 6 
You should document your implementation in accordance with the Programming Standards page on the course website.  It is 
possible that your implementation will be evaluated for documentation. 
 
If you make more than one submission, the final one will be graded.  Submissions after the due date will be penalized 10% 
per day, with a maximum late penalty of 50%. 
 
Since this assignment is due at the end of classes, we may not publish many rounds of score reports, so check your 
submission carefully. 
 
 
Pledge 
 
Each of your program submissions must be pledged to conform to the Honor Code requirements for this course.  Specifically, 
you must include the following pledge statement at the beginning of the file that contains main(): 
 
//    On my honor: 
//    
//    - I have not discussed the Java language code in my program with 
//      anyone other than my instructor or the teaching assistants 
//      assigned to this course. 
//    
//    - I have not used Java language code obtained from another student, 
//      or any other unauthorized source, including the Internet, either 
//      modified or unmodified.  
//    
//    - If any Java language code or documentation used in my program 
//      was obtained from another source, such as a text book or course 
//      notes, that has been clearly noted with a proper citation in 
//      the comments of my program. 
//    
//    - I have not designed this program in such a way as to defeat or 
//      interfere with the normal operation of the supplied grading code. 
// 
//     
//     
 
I reserve the option of assigning a score of zero to any submission that is undocumented or 
does not contain this statement. 
 
Change Log 
 
Version Date Page Change(s) 
5.00 April 20   Base document 
 
 
  
CS 3114  Data Structures and Algorithms  J5: Dijkstra's Shortest Path Algorithm with Min-heap 
 
Version 5.00 This is a purely individual assignment! 7 
Notes 
 
[1] Each entry in the grid corresponds to the weight of an edge in the graph.  The row number specifies the source vertex for 
that edge, and the column number specifies the terminal vertex for that edge. 
 
[2] I did not write generics for any of my data structures (weighted adjacency list, min-heap, Dijkstra table, path table); that's 
not to say I didn't make use of some of the generics in the Java Library. 
 
[3] You will probably discover, when you think about your implementation, that there's some virtue in a more sophisticated 
approach; see the following discussion about how to integrate a min-heap into the system. 
 
[4] These displays of the Dijkstra table were actually generated by my code; since I wrote a class for the Dijkstra table, I 
provided it with a display method.  I did the same with my min-heap.  That allowed my code to provide an accurate 
rendition of what was actually going on, from the perspective of the Dijkstra table and the min-heap, as the program ran.  
I found that to be useful when debugging my solution. 
 
[6] That is, the pointers are moved around in the array for the min-heap, but each pointer points to the same vertex object it 
was connected to at the beginning. 
 
[7] In graph theory, it's common to view a path as a sequence of edges, where the terminal vertex of each edge matches the 
 
[7] In graph theory, it's common to view a path as a sequence of edges, where the terminal vertex of each edge matches the 
source vertex of the next edge.  But, one can also view a path as just a sequence of vertices, where the edges are implied 
by the order of the vertices.  That is not necessarily the best approach when edges actually have attributes like weights. 
 
 [8] A flat zip file is one that includes no directory structure.  In this case, you can be sure you've got it right by copying your 
zip file to a new directory and unzipping it.  If that creates any subdirectories, your zip file is not flat, and it will not work 
with the grading scripts that will be used. 
 
Exception:  if you used packages, then your zip file must reconstruct the necessary directory tree when it's unpacked.  If 
you take this approach, be sure that your main class file, SSAD.java, is not in a subdirectory when your zip file is 
unpacked, and that the class SSAD is not in a package.