Description of the Lab

Overview of the Lab

In this Lab, we program Dijkstra’s algorithm to grab a single piece of cheese in the maze with mud.

As you will see in the articles of this Episode, Dijkstra’s algorithm is quite similar to the breadth-first search. Therefore, you should draw inspiration from the code you wrote during Lab 3.

Set up the environment

As always, you should start by duplicating the PyRat template file on Google Colab. For recall, you should go on the Google Colab template program, click on « File », then « Save copy in drive ». Rename it as dijkstra.ipynb, and make it accessible by link. We will refer to this link as <shared_link_to_dijkstra.ipynb>.

In this Lab, we will use the following command:

python pyrat.py --rat "<shared_link_to_dijkstra.ipynb>" -p 1 -x 15 -y 15 -d 0.5 --random_seed 1

Contrary to Lab 3, we allow some mud in the maze. Additionally, we reduce a bit the density of walls (-d option) to visualize if the rat indeed avoids mud when it has the opportunity to go faster by skirting it.

Dijkstra’s algorithm

There are multiple ways of coding Dijkstra’s algorithm, depending on which data structure is used. You could for instance maintain a list of vertices to visit, along with their distances to the initial vertex. However, some data structures exist which are more adapted to what we want to do here — always popping the closest unvisited vertex –, such as priority queues (min-heaps).

Priority queues

The Python heapq library makes it easy to create a priority queue. Here is a link to the official documentation.

With this module, you can create a priority queue as a list, as follows:

import heapq
priority_queue = []

The elements are added to the queue via the heappush function, and removed via the heappop function. This last function returns (by removing it from the structure) the minimum element.

To add an item in the list, simply insert a tuple into the priority queue, with the value as first entry, as follows:

import heapq
priority_queue = []
heapq.heappush(priority_queue, (18, "a"))
heapq.heappush(priority_queue, (15, "b"))
heapq.heappush(priority_queue, (16, "c"))
min_value, min_key = heapq.heappop(priority_queue)
print(min_value, min_key) # 15 b
print(priority_queue) # [(16, 'c'), (18, 'a')]

Dijkstra’s algorithm

Adapting the BFS you programmed in Lab 3, and using the heapq module introduced above, you should now be able to program Dijkstra’s algorithm.

We insist again on the fact that you should test that your program indeed finds the shortest path to the only piece of cheese. You should work on controlled mazes (use the random_seed option) and check at hand if everything goes well.