Objectives of the Episode
In this episode, we slightly increase the difficulty by introducing mud inside the maze. Two adjacent locations in the maze that are separated with mud require more than one unit of time to reach, and therefore cause the character to slow down.
In order to move inside this muddy maze, we introduce Dijkstra’s algorithm. This algorithm finds the shortest paths between a starting location and all other locations in the maze.
For implementing it, we introduce a new data structure: min heaps. We finally give a first introduction to notions of algorithmic complexity.
Articles to study before the Lab
Test your knowledge of this Episode by taking the following quiz.
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.
Work to do for the next episode
- Finish the implementation of the program in Lab 3;
- Study the articles of Episode 4.