Java程序辅导

School of Computer Science & Software Engineering
The University of Western Australia
Crawley, Western Australia, 6009.
CRICOS Provider Code: 00126G
CITS3210 Algorithms Laboratory sheet 3
These exercises are worth 2.5% of your final grade and are due at 5pm, Friday,
September 14, 2012
Use the Graph class, and Path interface provided on the unit web-page to implement solutions to the
minimum spanning tree problem (for wighted undirected graphs) the single source shortest path problem
(for weighted directed graphs), and the all pairs shortest path problem (for weighted undirected graphs).
Write a class PathImp that implements Path.
1. Your implementation of getMinimumSpanningTree should return the weight of the minimum span-
ning tree, or -1 if no minimum spanning tree can be found.
2. Your implementation of getShortestPaths(G, v) should use Djikstra’s algorithm to return an
array of the distances from the specified start vertex to each of the vertices in the graph.
3. Your implementation of getAllShortestPaths(G) should use a dynamic algorithm to return a two
dimensional array given the length of the shortest path between any two vertices (or -1 if there is
no shortest path).
The class PathTest is provided onthe unit web-page and allows you to either specify a graph from an
input file, or generate a random graph, on which you can run the algorithm.
Example output is
Input Graph (adjacency matrix)
10
5 16 5 8 19 9 8 1 5 8
16 10 19 7 7 5 15 4 7 18
5 19 1 7 1 20 12 15 9 2
8 7 7 14 11 18 13 5 11 14
19 7 1 11 0 15 10 17 0 8
9 5 20 18 15 0 11 20 10 7
8 15 12 13 10 11 8 14 20 20
1 4 15 5 17 20 14 12 0 8
5 7 9 11 0 10 20 0 5 7
8 18 2 14 8 7 20 8 7 15
1
MST weight: 36
Shortest paths from 0
0 5 5 6 6 9 8 1 5 7
All Shortest Distances:
0 5 5 6 6 9 8 1 5 7
5 0 8 7 7 5 13 4 7 10
5 8 0 7 1 9 11 6 9 2
6 7 7 0 8 12 13 5 11 9
6 7 1 8 0 10 10 7 10 3
9 5 9 12 10 0 11 9 10 7
8 13 11 13 10 11 0 9 13 13
1 4 6 5 7 9 9 0 6 8
5 7 9 11 10 10 13 6 0 7
7 10 2 9 3 7 13 8 7 0
Note that as an automated marker is used you will not be able to include print statements, java.util classes
etc in your implementation. However, a test class PathTest.java is available for your convenience.
Submit the file PathImp.java to https://secure.csse.uwa.edu.au/run/cssubmit. There is an au-
tomated script that will compile and run your code, and estimate your final mark. This feedback ensures
that you will not lose marks for small errors, but is no substitute for your own thorough testing.
2