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 efficiently 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, represented as a weighted graph.
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!
Lab instructions
Follow this link for the Lab contents!
Work to do for the next episode
- Finish the implementation of the program in Lab 4;
- Study the articles of Episode 5.