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.