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
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.
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')]
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.