Skip to main content

Module 6 · Dijkstra's Algorithm (Optional)

Module 6 · Dijkstra's Algorithm

The Same Algorithm, One Upgrade

15–20 minOptional module · 1–2 weeksAfter Module 5Slides (PowerPoint)
👩‍🏫

Teacher mode is on — the gray boxes are yours only. Flip the switch (bottom-right) to preview the student view.

Module 5 ended with a robot that finds its own way around blocked intersections. It uses breadth-first search, which finds the path with the fewest steps, and on a grid where every block takes the same time, that is also the fastest path.

But what if one block doesn't take the same time? Suppose one segment of the grid takes a long, winding detour between two intersections, so that driving it takes as long as five ordinary blocks. The map still says it's one step. BFS will happily send the robot down it, because BFS only counts steps.

This module fixes that. Dijkstra's algorithm is your BFS with two changes, and it finds the path that takes the least time, not the fewest steps.

A 4 by 4 grid with one slow, winding segment between (0, 1) and (0, 2), on the left edge. BFS goes straight up the left edge through it: 3 steps, cost 7. Dijkstra goes around through x = 1: 5 steps, cost 5.
The same trip, two planners. BFS counts steps and takes the slow road; Dijkstra adds up time and goes around it.

Learning Objectives

By the end of this module you will be able to:

  • Measure a slow segment and turn it into a number: its weight
  • Add a cost check to the Module 5 test harness, and show BFS failing it
  • Turn your compute_bfs_path() into compute_dijkstra_path() by making two changes to a copy
  • Read a cost grid and explain every number on it
  • Run three planners through one harness and say exactly where they agree and disagree

What this module is not​

It is not a new kind of programming. There is no new Python syntax in it. The graph, add_blocked(), the previous dictionary, the walk-back and the harness are all the ones you built in Module 5, in the same robot.py — the harness gains one case, and the file gains two sections above RUN: WEIGHTED GRAPH and DIJKSTRA PLANNER. The two changes are in the middle of one function:

  1. Take the closest intersection off the to-visit list instead of the oldest one.
  2. Add the segment's weight instead of counting one step, and keep the cheaper total if you reach the same place a second time.

That's it. The rest of the module is about seeing why those two changes matter.

The lessons​

LessonWhat happens
6-1 · When Fewest Steps Isn't FastestTime a normal block and the slow segment with a stopwatch. Work out, on paper, which of two routes is really faster.
6-2 · Weights in the GraphStart the WEIGHTED GRAPH section: the slow list, weight(), path_cost() and a cost check. Run the check on BFS — and watch it fail.
6-3 · From BFS to DijkstraStart the DIJKSTRA PLANNER section: copy your BFS, rename it, make the two changes. Print the cost grid. Run Manhattan, BFS and Dijkstra through the same harness.
6-4 · Drive ItThe robot on the slow-segment grid: a BFS run, then a Dijkstra run, one test and one changed name.
6-5 · Three Planners, One Harness (optional extension)The Dijkstra class, and all three planners as objects through the Module 5 class harness.
Knowledge Check

On a grid where every segment takes the same time, how do BFS and Dijkstra's algorithm compare?

Resources​