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 of this Episode, Dijkstra’s algorithm is quite similar to the breadth-first search. Therefore, we are going to re-use what we did before.
Dijkstra’s algorithm
Set up the environment
First, create a new PyRat file called dijkstra.py (you can duplicate your dfs.py file as contets will be very close). Also, make a backup file (a copy) of your bfs.py file from the previous Episode, just in case, as we are going to edit it.
Then, make sure that your configuration reflects what we are going to test here, i.e., that there is one cheese and some mud.
#################################################################################################################
###################################################### GO ! #####################################################
#################################################################################################################
if __name__ == "__main__":
# Map the functions to the character
players = [{"name": "Dijkstra", "preprocessing_function": preprocessing, "turn_function": turn}]
# Customize the game elements
config = {"maze_width": 15,
"maze_height": 11,
"mud_percentage": 40.0,
"nb_cheese": 1,
"trace_length": 1000}
# Start the game
game = PyRat(players, **config)
stats = game.start()
# Show statistics
print(stats)
#################################################################################################################
#################################################################################################################
Implementation particularities
There are multiple ways of coding Dijkstra’s algorithm. In the course video, you are given an algorithm that uses a function named add_or_replace, that adds an element to the priority queue if not there, or replaces it if already there.
Here, we are going to use a Python implementation for priority queues, provided by the library heapq. Contrary to the course, this library does not implement that add_or_replace function, so we will need to adapt the algorithm seen in the course.
Remember: to address a problem, we first need to formalize, then define/choose an algorithm, and finally implement it. Sometimes, there are differences between the algorithm and the code, due to library/hardware… constraints. This is the case here.
So, how are we going to adapt? Here, as you will see below, adding an element to the priority queue will keep its duplicate in the structure (if any). For Dijkstra’s algorithm, this corresponds to multiple candidate paths leading to a same vertex in the graph. However, you are only interested in the shortest of those paths.
You should remember that, when popping an element, you will always get the one with the smallest value. Therefore, if a vertex appears multiple times in the structure, with different values, you are only interested in the first time you pop it. Consequently, when popping a vertex, you can determine if a shorter path to it was already explored if the vertex was already marked as visited. In that case, you can just ignore the pop call.
The heapq library
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, (20, "c")) 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'), (20, 'c')]
Dijkstra’s algorithm
Using the heapq library, edit your dijkstra.py file and define the functions to create a priority queue, add an element to it, and pop an element from it, as follows:
def dijkstra ( source: int,
graph: Union[numpy.ndarray, Dict[int, Dict[int, int]]]
) -> Tuple[Dict[int, int], Dict[int, Union[None, int]]]:
"""
Dijkstra's algorithm is a particular traversal where vertices are explored in an order that is proportional to the distance to the source vertex.
In:
* source: Vertex from which to start the traversal.
* graph: Graph on which to perform the traversal.
Out:
* distances_to_explored_vertices: Dictionary where keys are explored vertices and associated values are the lengths of the paths to reach them.
* routing_table: Routing table to allow reconstructing the paths obtained by the traversal.
"""
# Function to create an empty priority queue
def _create_structure ():
# TODO: Fill here
# Function to add an element to the priority queue
def _push_to_structure (structure, element):
# TODO: Fill here
# Function to extract an element from the priority queue
def _pop_from_structure (structure):
# TODO: Fill here
# Perform the traversal
distances_to_explored_vertices, routing_table = traversal(source, graph, _create_structure, _push_to_structure, _pop_from_structure)
return distances_to_explored_vertices, routing_table
Then, if necessary, update the traversal function in your bfs.py file so that Dijkstra’s algorithm works just as your BFS and DFS before.
Test!
Now, as usual, you should write the unit tests for your Dijktra’s algorithm. Think of interesting scenarios to make sure it works, and avoids mud when neede, crosses some when needed, etc.
Also, now that you have changed your traversal file, it is important that you test that it still works for your previous code. Indeed, the modifications you made may have impacted your previous code. Therefore, for maintaining compatibility, make sure that your previous tests for the BFS and DFS still work as expected.