Contents of the page


Description 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 above, Dijkstra’s algorithm is quite similar to the breadth-first search. Therefore, you should draw inspiration from the code you wrote during Lab 2.

The command line we are going to use is the following, assuming your program is named AIs/dijkstra.py:

python pyrat.py --rat AIs/dijkstra.py -p 1 -x 15 -y 15 -d 0.5

Contrary to Lab 2, 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.

Priority queues

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

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 couple 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 2, using the heapq module introduced above, you should new 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 and check at hand if everything goes well.