4. Maze escape
Worth: 5%
DUE: April 5th, 2022 at 11:55pm; submitted on MOODLE.
Warning
This is an individual assignment.
In this assignment you need to create a program that will find the shortest path through a maze.
For the same graph you will compare the shortest path without weights and with weights.
4.1. Maze
We can represent a maze by a graph if we place nodes at each intersection and at each dead end.
For example, if we take the following maze:
We can create the following graph representation:
4.2. Instructions
The program should be able to read a file containing the graph, as done in the lab.
The graph should be represented by a class implementing the interface
Graph
see in class:It can be the adjacency list representation of the matrix representation.
You need to use Breadth First Search and dijkstra’s algorithm to calculate the shortest paths.
Both algorithms need to be implemented in their own class.
At the end the program should print both path.
4.3. Implementation
You need to have the following classes:
Main
: the class will run the entire program and will print the paths.Your class implementing the interface
Graph
.You can use
ListGraph
if you want.
BreadthFirstSearch
: the class implementing Breadth First Search.Dijkstra
: The class implementing Dijkstra’s algorithm.
4.4. Some marking details
Warning
Having the correct outputs doesn’t mean that you will obtain a perfect mark.
The marking will depend on:
Correctness.
Comments
Variable names
Style
etc.