Lesson 3 · Dijkstra's Algorithm — The Concept

Module 5 · Dijkstra's Algorithm

Lesson 3 · Dijkstra's Algorithm — The Concept

55 minNo codingHand-trace on paper

👩‍🏫

Teacher mode is on. Toggle it off (bottom-right) to preview the student view.

This is the algorithm GPS systems use to find the shortest route — invented by Edsger Dijkstra in 1956 and still in use today. You'll learn it the way you learned Manhattan: by hand, on paper, before writing a line of code. Trace it a few times and the code in Lessons 4–5 will feel like transcription.

Learning Objectives

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

• Name the three data structures: distances, previous, and visited
• Explain what each one stores
• Trace the algorithm step by step on a small grid
• Pick the correct next node (smallest distance, unvisited)
• Reconstruct the shortest path from previous

📄

Printable knowledge checks — the 5 questions from this lesson on one page, with room to write. Teachers: answer key.

The three data structures

Dijkstra explores outward from the start, always visiting the nearest unvisited node next. It keeps track of everything with three structures:

• distances — a dictionary of the shortest known distance from the start to each node. Start is 0; everything else begins at "infinity" (we'll use a big number).
• previous — a dictionary of which node you came from to reach each node. Used to rebuild the path. Start's previous is None.
• visited — a list of nodes already finished. Once visited, a node's distance is final.

distances = {(0,0): 0}      # start is 0 steps from itself
previous  = {(0,0): None}    # nothing comes before the start
visited   = []               # nothing finished yet

Knowledge Check

What does the previous dictionary store?

The algorithm in one sentence

Repeat: pick the unvisited node with the smallest distance, update its neighbors, then mark it visited — until the destination is visited.

More precisely, each round:

1. Among unvisited nodes with a known distance, pick the one with the smallest distance — call it current.
2. For each unvisited neighbor of current: if going through current is shorter than the neighbor's current distance, update its distance and set its previous to current.
3. Mark current visited.

The key decision is step 1: you always visit the closest-to-start node next — not the one closest to the destination.

Knowledge Check

Which unvisited node does Dijkstra visit next?

Activity · Trace it: 3×3 with (1,1) blocked

Find the shortest path from (0,0) to (2,2), with (1,1) blocked:

(0,0) --- (0,1) --- (0,2)
  |                   |
(1,0)               (1,2)
  |                   |
(2,0) --- (2,1) --- (2,2)

Work it one row at a time. Each round: pick the unvisited node with the smallest distance, update its neighbors, mark it visited. The first row is done for you — carry on until the destination is visited. Keep this table: you'll use it as a test case in Lessons 4 and 5, so it has to be yours.

Step	Visit	Dist	Updates neighbors	visited grows to
1	(0,0)	0	(0,1)=1, (1,0)=1	[(0,0)]
2
3
4
5
6
7
8

Notice (1,1) never appears — a blocked node simply isn't in the graph, so the algorithm never touches it.

Knowledge Check

At step 7, visiting (2,1) offers (2,2) a distance of 3+1=4, but (2,2) already has distance 4. What happens?

Reconstruct the path

The previous dictionary rebuilds the route — trace backward from the destination. Here's the technique on a tiny 1×3 strip, so you can see the mechanics without giving away your own trace:

previous: {(0,0): None, (0,1): (0,0), (0,2): (0,1)}

start at the destination (0,2)
(0,2) ← (0,1) ← (0,0)      # (0,0)'s previous is None → stop

That gives [(0,2), (0,1), (0,0)] — backward, because you followed the arrows from the end. Reverse it for the route the robot actually drives: [(0,0), (0,1), (0,2)].

Now do the same with your table from the activity above. Write out the previous entry you recorded for each node, start at (2,2), follow it back to (0,0), and reverse.

Compared to Manhattan: on a clear grid, Dijkstra finds a path of the same length as Manhattan (the exact route may differ). Its advantage isn't shorter paths — it's that it works with obstacles.

Knowledge Check

Why must the reconstructed path be reversed?

Real-world connections

Dijkstra and its relatives are everywhere shortest paths matter:

Maps

GPS routing

Turn-by-turn directions come from shortest-path algorithms descended from Dijkstra's.

Networks

Internet packets

Routers use shortest-path algorithms to move data efficiently across the network.

Games

Enemy AI

Game characters find their way around walls and obstacles with graph search like this.

Wrap-up

• What are the three data structures and what does each hold? (distances, previous, visited — shortest distances, predecessors, and finished nodes.)
• How do you choose the next node? (Smallest known distance among unvisited.)
• Why reverse the reconstructed path? (You trace it backward from the destination.)

The hardest lesson in the module — go slow, use the board

Write the full state (distances / previous / visited) after every step; students must see the structures change. Ask "which node next?" each round and make them answer before you proceed — that's the core skill. The #1 confusion: they want to visit the node nearest the destination; reinforce that it's smallest distance from the start. Emphasize that blocked nodes simply aren't in the graph — the algorithm doesn't "skip" them, they're absent. Path reconstruction feels backward; connect it to "how did you get here?" (you hear the last step first). Save every completed trace — they're the test cases for Lessons 4 and 5.

Wrap-up quiz

Knowledge Check

On a clear grid with no obstacles, how does Dijkstra's path length compare to Manhattan's?

Assessment & next lesson

Formative: name the three structures, pick the right next node, update neighbors correctly, and reconstruct a path. Exit ticket: "Given previous = {(0,0): None, (0,1): (0,0), (1,1): (0,1)}, reconstruct the path from (0,0) to (1,1)." ([(0,0),(0,1),(1,1)]). Preview: next lesson we start building the Dijkstra class — constructor and graph now, the algorithm in Lesson 5.

Resources

• XRPLib Documentation
• Dijkstra's algorithm