Skip to main content

Lesson 1 · The Grid as a Graph

Module 5 · Dijkstra's Algorithm

Lesson 1 · The Grid as a Graph

45–50 minNo codingMental model first
👩‍🏫

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

Your Manhattan robot always goes rows-first, then columns. But what happens when an intersection on that route is blocked? It has no way around. This module fixes that — and it starts by seeing the grid a new way: as a graph of nodes and edges. No code today, just paper and the physical grid.

Learning Objectives

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

  • Define node, edge, and neighbor
  • Explain why a grid of intersections is a graph
  • Remove a blocked node (and its edges) from a graph
  • Find a shortest path by hand that detours around obstacles
  • Explain why the Manhattan algorithm can't handle blocked intersections
Printable knowledge checks — the 5 questions from this lesson on one page, with room to write. Teachers: answer key.

Why Manhattan isn't enough​

Your usual route to school is closed for construction. You don't give up — you find a detour, and your GPS reroutes you automatically. The robot needs to do the same.

The Manhattan algorithm from Module 4 only knows one strategy: rows first, then columns. It has no concept of an obstacle. If the intersection it wants to drive through is blocked, it drives right into it. To route around things, we need a smarter way to think about the grid.

Knowledge Check

Why can't the Manhattan algorithm route around a blocked intersection?

Nodes, edges, neighbors​

A graph is a collection of nodes (points) connected by edges (links). You already know graphs: a road map (intersections + streets), a social network (people + friendships), airline routes (airports + flights). A graph captures what connects to what.

Our grid is a graph. Every intersection is a node, named by its coordinate like (1, 2). Every line between two adjacent intersections is an edge. The nodes an edge connects you to are that node's neighbors.

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

How many neighbors a node has depends on where it sits: a corner has 2, an edge node has 3, an interior node has 4.

Knowledge Check

On a 3×3 grid, how many neighbors does the interior node (1,1) have?

Blocking a node​

When an intersection is blocked, we remove it from the graph entirely — the node and all its edges. Block (1,1) on the 3×3 grid:

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

(1,1) is gone, and every node that used to touch it — (0,1), (1,0), (1,2), (2,1) — has lost a neighbor. Blocking one node changes its neighbors too.

Knowledge Check

After (1,1) is blocked, how many neighbors does (0,1) have?

Activity · Finding a path around​

Now block (1,0) instead, and find the shortest path from (0,0) to (2,0):

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

Manhattan would try (0,0) → (1,0) → (2,0) — but (1,0) is blocked, so it fails. Trace a way around with your finger and count the steps before reading on.

Without the obstacle, the Manhattan distance is only 2. Obstacles make paths longer — and Manhattan distance becomes just a lower bound, not the real answer.

One more idea for later: our grid is unweighted — every edge costs 1 step. (In a weighted graph, a highway edge might cost less than a side-street edge.) Dijkstra's algorithm handles both; we'll use the unweighted case.

Knowledge Check

With (1,0) blocked, the shortest path from (0,0) to (2,0) is 4 steps, but the Manhattan distance is 2. What does that tell you?

Real-world connections​

Graphs run a huge amount of the technology you use:

Navigation

GPS & Waze

Roads are edges, intersections are nodes. Rerouting around a closure is exactly this graph problem.

Social

Friend networks

People are nodes, friendships are edges — "friends of friends" is a graph search.

Internet

Network routing

Data hops between routers (nodes) over links (edges), picking a shortest path each time.

Wrap-up​

  • What are a node, an edge, and a neighbor? (A point, a link between adjacent points, and the points a node links to.)
  • What happens to the graph when a node is blocked? (It's removed entirely — node and all its edges.)
  • Why can obstacles make a path longer than the Manhattan distance? (You have to detour around blocked nodes.)

Wrap-up quiz​

Knowledge Check

In computer science, what does the word 'graph' mean?

Resources​