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

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:

.. figure:: ./maze/maze.drawio.png
    :align: center

|

We can create the following graph representation:

.. figure:: ./maze/maze_graph.drawio.png
    :align: center

|

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 :code:`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.

Implementation
==============

*  You need to have the following classes:

   *  :code:`Main`: the class will run the entire program and will print the paths.
   *  Your class implementing the interface :code:`Graph`.

      *  You can use :code:`ListGraph` if you want.
   
   *  :code:`BreadthFirstSearch`: the class implementing Breadth First Search.
   *  :code:`Dijkstra`: The class implementing Dijkstra's algorithm.

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.