Practical activity

Duration2h30

Presentation & objectives

In this activity, you will have to develop a solution to grab a single piece of cheese in a maze with mud. To do this, we propose to use Dijkstra’s algorithm.

Contrary to the previous activities, you will be a lot less guided. We only provide you general directions, the rest is up to you.

Activity contents

1 — Dijkstra’s algorithm

1.1 — Get prepared

Before we start, let’s first create the files we need in the workspace:

  • pyrat_workspace/players/Dijkstra.py – Duplicate the file TemplatePlayer.py, and rename it Dijkstra.py. Then, as in the previous session, rename the class to Dijkstra.

  • pyrat_workspace/games/visualize_Dijkstra.ipynb – Create a file that will start a game with a Dijkstra player, in a maze with mud (argument mud_percentage), and a single piece of cheese (argument nb_cheese). Optionally, you can set a random_seed and a trace_length. You should draw inspiration from the other files in the games subdirectory you encountered in the previous session.

  • pyrat_workspace/tests/tests_Dijkstra.ipynb – Drawing inspiration from the test_DFS.ipynb and test_BFS.ipynb files you encountered in the previous session, create a test_Dijkstra.ipynb file. This file will contain the unit tests you will develop to test Dijkstra’s algorithm.

1.2 — Program Dijkstra’s algorithm

You already know that Dijkstra’s algorithm can be used to reach that goal. Check the articles you studied until now, or other online resources, as you prefer!

Below are a few things you should do.

1.2.1 — Identify functions

Last time, when programming the BFS and DFS algorithm, we identified a few subroutines we could use as functions. Indeed, we created methods traversal and find_route. Separating the whole thing into these two blocks made it easier for us to write unit tests and reach a fully functional code.

You should first take a time to think of what methods you need to write Dijkstra’s algorithm. Also, what should be their inputs? And what output should they produce? When done, write their prototypes (i.e., the def line, and a placeholder return if necessary) in your Dijkstra.py player file.

1.2.2 — Program and test

Once this is done, there are two schools:

  • Classical approach – The most usual way of developing a program is to program the body of a method, and then to test it. Once validated, go on with the next method, etc., until all methods are programmed.

  • Test-driven development – If you prefer, before coding the contents of your methods, you can already write the unit tests in test_Dijkstra.ipynb. This will allow you to test your methods more frequently when you develop them, and you can be convinced of your work when it passes all the tests you previously designed.

In all cases, you should take a moment to think and list the unit tests you want to perform. For each test, we invite you to determine if it corresponds to a normal usage, or to a possible error.

Important

It is important that you accurately design tests that convince you your program works as expected!

For example, let’s assume you want to design a test to make sure that Dijkstra finds the shortest path in a weighted graph, contrary to a BFS. Intuitively, you want to create a fixed graph, identify the shortest path at hand, and verify that Dijkstra’s output will be equal to that path. However, the choice of graph you will use has a lot of importance:

  • If you choose a maze in which there is only a single path from your initial location to the piece of cheese, then both BFS and Dijkstra’s algorithm will find the correct path.

  • Similarly, if there is no mud along the shortest path from your initial location to the piece of cheese (or it is always faster to cross that mud than to avoid it), then again both BFS and Dijkstra’s algorithm will find the correct path.

1.2.3 — What should it look like?

The following video shows you an example of what you should observe:

Don’t hesitate to compare with the other videos in the previous session to check the differences. In particular, note that the rat followed the path [97, 98, 99, 114, ...] instead of [97, 112, 113, 114...] to avoid a mud. Try to run your BFS.py player on a weighted maze too to check the difference (use the random_seed argument to keep the same maze).

To go further

2 — Compare with the other traversals

As before, an easy thing you can do now is to compare all RandomX.py, DFS.py, BFS.py and Dijkstra.py on weighted graphs. You can adapt the previous script compare_all_randoms.ipynb (or whatever you renamed it to) to do that.

Then, try to answer the following questions:

  • Does Dijkstra’s algorithm reduce significantly the number of turns needed to grab a piece of cheese compared to a BFS?

  • Is it the case for all values of mud_percentage? If not, what is the minimum percentage of cells separated with mud you need to have in the maze to make it significant?

  • Does it depend on the mud_range option?

3 — Factorize codes

If you went through the optional part of last session, you should have factorized your BFS.py and DFS.py into a class Traversal from which you derive two classes BFSTraversal and DFSTraversal.

  • With possibly a few adaptations in Traversal.py, can you create a class DijkstraTraversal that inherits from Traversal? Here is the UML diagram from session 2, with that new class:

  • If you manage to do it, adapt the enumeration and constructor in TraversalPlayer.py to add the option to use Dijkstra’s algorithm.

To go beyond

4 — The Floyd-Warshall algorithm

Dijkstra’s algorithm is what we call a “1-to-*” algorithm. This means that it will find the shortest paths from a single initial location to all other locations in the graph.

The Floyd-Warshall algorithm is what we call a “*-to-*” algorithm. It will simultaneously compute all shortest paths from all vertices to all vertices.

  • Read a bit about this algorithm. Should you use it in the project?

    Correction

    Let $n$ be the number of vertices in the graph (cells in the maze).

    In a PyRat maze, Dijkstra’s algorithm has a complexity of $O(n \cdot log(n))$. Therefore, if we run it from each possible start ($n$ times), we obtain a complexity of $O(n^2 \cdot log(n))$.

    As the Floyd-Warshall algorithm has a complexity of $O(n^3)$, using Dijkstra’s algorithm multiple times is preferable.

  • If you want, you can try to implement that algorithm (or maybe find a library that does it?).

5 — The Bellman-Ford algorithm

The Bellman-Ford algorithm is also a “1-to-* algorithm. However, contrary to Dijkstra’s algorithm, it has the property to be able to find the shortest path if some edges are negatively weighed. Also, it can be used to detect an absorbing cycle in the graph.

  • Read a bit about this algorithm. Should you use it in the project?

    Correction

    The Bellman-Ford algorithm has a complexity of $O(mn)$, with $n$ the number of vertices in the graph and $m$ the number of edges in the graph. In the case of a PyRat game, each vertex has at most 4 neighbors. Therefore, in that particular case, the Bellman-Ford algorithm has a complexity of $O(4n \cdot n)$, or $O(n^2)$.

    Since we do not have negative weights in a PyRat maze (which would justify the choice of the Bellman-Ford algorithm), Dijkstra’s algorithm is preferrable.

  • If you want, you can try to implement that algorithm (or maybe find a library that does it?).

6 — Johnson’s algorithm

Johnson’s algorithm is a “*-to-*” algorithm, that exploits the Bellman-Ford algorithm to find all shortest paths in the graph.

  • Read a bit about this algorithm. Should you use it in the project?

    Correction

    Johnson’s algorithm has a complexity of $O(n^2 \cdot log(n) + mn)$, with $n$ the number of vertices in the graph and $m$ the number of edges in the graph.

    Compared to Dijkstra’s complexity of $O(n^2 \cdot log(n))$, and since we do not have negative weights in a PyRat maze (which would justify the choice of Johnson’s algorithm), multiple calls to Dijkstra’s algorithm are preferrable.

  • How does it compare to the Floyd-Warshall algorithm?

  • If you want, you can try to implement that algorithm (or maybe find a library that does it?).