Skip to main content

Lesson 4 · The Dijkstra Class

Module 5 · Dijkstra's Algorithm

Lesson 4 · The Dijkstra Class

55 minPython classesStructure first
👩‍🏫

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

Time to turn the concept into code — but in stages. This lesson builds the class structure: the constructor, the instance variables, and build_graph (which creates the grid and removes blocked nodes). The compute_path algorithm itself waits until Lesson 5. The class is designed as a drop-in replacement for Manhattan — same method name, same return type — so the Navigator works with either.

Learning Objectives

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

  • Write the Dijkstra __init__ with start and blocked parameters
  • Store self.position, self.blocked, and self.graph
  • Implement build_graph, skipping blocked nodes and blocked neighbors
  • Write a compute_path placeholder that returns an empty list
  • Explain why Dijkstra's interface matches Manhattan's
Printable knowledge checks — the 5 questions from this lesson on one page, with room to write. Teachers: answer key.

A better toolbox​

In Module 4 you built the Manhattan class — a path planner for a clear grid. Dijkstra is a better one: same shape, but it can route around obstacles. Compare the constructors:

class Manhattan:
    def __init__(self, start):
        self.position = start

class Dijkstra:
    def __init__(self, start, blocked):
        self.position = start
        self.blocked = blocked
        self.graph = self.build_graph()

Two additions: a blocked list (the obstacles) and a graph (built immediately when the object is created). Notice __init__ calls build_graph() — so the graph is ready the moment you make a Dijkstra object.

Knowledge Check

When is self.graph built?

Activity · Build the Dijkstra class​

Three steps, the same shape as the Manhattan class: store what has to persist, stub out what you haven't written yet, and test the structure before you write any of the hard part.

Step 1 · build_graph — build and block in one pass​

This is the build_grid_graph idea from Lesson 2, adapted as a method that also skips blocked nodes. It does both jobs at once — skip a node if it's blocked, and only add a neighbor if that neighbor isn't blocked:

def build_graph(self):
    rows = 4
    cols = 4
    graph = {}
    for row in range(rows):
        for col in range(cols):
            if (row, col) in self.blocked:
                continue                                   # skip blocked node entirely
            neighbors = []
            if row > 0 and (row - 1, col) not in self.blocked:
                neighbors.append((row - 1, col))
            if row < rows - 1 and (row + 1, col) not in self.blocked:
                neighbors.append((row + 1, col))
            if col > 0 and (row, col - 1) not in self.blocked:
                neighbors.append((row, col - 1))
            if col < cols - 1 and (row, col + 1) not in self.blocked:
                neighbors.append((row, col + 1))
            graph[(row, col)] = neighbors
    return graph

Building and blocking together is cleaner than building the full graph and then removing nodes in a second pass — a blocked node never enters the graph at all.

Knowledge Check

What does `if (row, col) in self.blocked: continue` do?

Step 2 · The compute_path placeholder​

Build in stages: leave the algorithm as a placeholder so you can test the structure now.

def compute_path(self, destination):
    # TODO: implement Dijkstra's algorithm (Lesson 5)
    print(f"compute_path from {self.position} to {destination}")
    print(f"Graph has {len(self.graph)} nodes")
    return []

Returning an empty list of the right type means you can test __init__ and build_graph today without needing the algorithm yet.

Knowledge Check

Why leave compute_path as a placeholder for now?

Step 3 · Test the structure​

Create objects and check the graph against what you know from Lessons 1–2:

d = Dijkstra((0, 0), [])
print(len(d.graph))          # 16 (full 4×4 grid)
print(d.graph[(1, 1)])       # 4 neighbors

d = Dijkstra((0, 0), [(1, 1)])
print(len(d.graph))          # 15
print((1, 1) in d.graph)     # False
print(d.graph[(0, 1)])       # does NOT include (1,1)

Block two nodes and you get 14. Each blocked node vanishes from the keys and from every neighbor list.

Knowledge Check

On a 4×4 grid, how many nodes does Dijkstra((0,0), [(1,0),(2,1)]).graph contain?

The shared interface​

Here's the design payoff. Both classes offer compute_path(destination) returning a list of (row, col) tuples:

Module 4

Manhattan(start)

compute_path(destination) → list of tuples. Fast, but no obstacles.

Module 5

Dijkstra(start, blocked)

compute_path(destination) → list of tuples. Handles obstacles.

Because the interface matches, the Navigator can call pathfinder.compute_path(dest) without caring which class it holds. You'll swap them in Lesson 6.

Knowledge Check

Why does it matter that Dijkstra's compute_path returns the same type as Manhattan's?

Wrap-up​

  • What three things does __init__ store? (self.position, self.blocked, self.graph.)
  • What two jobs does build_graph do at once? (Builds the grid and excludes blocked nodes.)
  • Why does the interface match Manhattan's? (So Navigator can swap one for the other.)

Resources​