4. Maze escape

  • Worth: 5%

  • DUE: April 4th, 2024 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:

../_images/maze.drawio.png

We can create the following graph representation:

../_images/maze_graph.drawio.png

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.