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:

1. Apply Prim's algorithm to find a minimum spanning tree of an undirected, weighted graph.

2. Apply Dijkstra's algorithm to find the shortest paths from a source vertex in a directed, weighted graph.

Exercises

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) and the single source shortest path problem (for weighted directed graphs). Write a class PathImp that implements Path.

1. Your implementation of getMinimumSpanningTree should return the weight of the minimum spanning 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.

To help you test your code, a class PathTest is provided. It should give something similar to the output:
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