School of Computer Science and Software Engineering

# School of Computer Science and Software Engineering

## CITS2200 Data Structures and Algorithms

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, 8th May 2020.

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 cssubmit.

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.

# The University of Western Australia

## University information

CRICOS Code: 00126G