The exercises in this labsheet are worth 2.5% of your final mark in this unit.
The final date for submission is: 11:59pm Friday, May 12, 2023.
The aims of this labsheet are to:
Apply Prim's algorithm to find a minimum spanning tree of an undirected, weighted graph.
Apply Dijkstra's algorithm to find the shortest paths from a source vertex in a directed, weighted graph.
Graph
class, and Path
interface provided on the unit web-page to implement solutions to the minimum spanning tree problem (for wighted undirected graphs) and the single source shortest path problem (for weighted directed graphs). Write a class PathImp
that implements Path
.
getMinimumSpanningTree
should return the weight of the minimum spanning tree, or -1 if no minimum spanning tree can be found.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.
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
MST weight: 36
Shortest paths from 0
0 5 5 6 6 9 8 1 5 7
Fully document your code using javadoc
comments.
Submit your
PathImp
implementation to the correct folder in Moodle.
If submitted before the due date, the system will compile and run your code, estimate your mark, and provide you with feedback. Final marking will occur after the posted due date and is subject to further examination, testing, and plagiarism checks of your code. Note that for security reasons, your code cannot contain any I/O commands, including printing statements. Although the auto-marking program provides you with some feedback, it should not be used as a substitute for your own testing.
Sample solution for lab 8 is here