Skip to main content

Lesson 6 · Testing and Swapping

Module 5 · Dijkstra's Algorithm

Lesson 6 · Testing and Swapping

55 minTesting + designThe two-line swap
👩‍🏫

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

Your Dijkstra class works — now prove it, then experience the payoff of good design. Because Dijkstra and Manhattan share the same interface, you can drop Dijkstra into your Module 4 Navigator by changing two lines. The robot drives exactly as before, but now it can route around obstacles.

Learning Objectives

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

  • Write tests that verify Dijkstra matches Manhattan on a clear grid
  • Write tests that verify Dijkstra reroutes around blocked nodes
  • Explain what a shared interface is and why it matters
  • Swap Dijkstra into the Navigator by changing only the import and constructor
  • Explain polymorphism in plain terms
Printable knowledge checks — the 4 questions from this lesson on one page, with room to write. Teachers: answer key.

What makes a good test​

A good test has a known input, an expected output you worked out yourself, and a check that compares actual to expected. Test two scenarios: clear grids (Dijkstra should match Manhattan's length) and grids with obstacles (Dijkstra should detour).

d = Dijkstra((0, 0), [])
path = d.compute_path((3, 3))
print("Path:", path)
print("Steps:", len(path) - 1)     # expect 6 — the Manhattan distance

On a clear 4×4 grid, the path from (0,0) to (3,3) is 6 steps. The route Dijkstra picks may differ from Manhattan's, but the step count must match — because there are many shortest paths of equal length.

Knowledge Check

On a clear grid, why check the step count rather than the exact path?

Activity · Test the obstacle case​

Block a node on the direct route and confirm Dijkstra both detours and never steps on a blocked node:

blocked = [(1, 0), (2, 2)]
d = Dijkstra((0, 0), blocked)
path = d.compute_path((3, 3))
print("Path:", path)

for node in path:
    if node in blocked:
        print("ERROR: path goes through", node)
        break
else:
    print("PASS: path avoids all blocked nodes")

That for/else is handy: the else runs only if the loop finishes without break — so it prints PASS only when no blocked node was found.

Knowledge Check

In a for/else loop, when does the else block run?

Activity · The two-line swap​

Here's the reward for building Dijkstra with Manhattan's interface. Your Module 4 program created a Manhattan planner:

from manhattan import Manhattan
pathfinder = Manhattan((0, 0))
# ... navigator uses pathfinder.compute_path(dest)

Change two lines to use Dijkstra — the import and the constructor:

from dijkstra import Dijkstra
pathfinder = Dijkstra((0, 0), [])     # add a blocked list
# ... EVERYTHING ELSE STAYS THE SAME

The Navigator still calls pathfinder.compute_path(dest) exactly as before. It doesn't know — or care — which planner it's holding.

Knowledge Check

How many lines of the Navigator's own code change to use Dijkstra instead of Manhattan?

Shared interface = polymorphism​

When two classes offer the same method names, parameters, and return types, code that uses one automatically works with the other. That's a shared interface, and the ability to swap them is called polymorphism ("many forms").

Everyday

USB-C

One connector, many devices. The port doesn't care what's plugged in — same interface.

Everyday

Power outlets

Any appliance with a standard plug works in any outlet. Shared interface, swappable devices.

Code

Pathfinders

Navigator + compute_path() = any planner that fits the interface. Manhattan or Dijkstra, its choice.

You've been using polymorphism the moment you swapped planners — the fancy word is just a label for something simple: if two things work the same from the outside, use either.

Knowledge Check

The swap works because Dijkstra is 'better' than Manhattan. True or false?

Wrap-up​

  • What three parts make a good test? (Known input, hand-calculated expected output, a check.)
  • What two lines change to swap in Dijkstra? (The import and the constructor.)
  • What is a shared interface, and what's the swap ability called? (Same method signature/return; polymorphism.)

Note on the interface​

Both planners take a start when created and a destination in compute_path: Manhattan((0,0)) and Dijkstra((0,0), []) both answer compute_path((3,3)) with a list of grid tuples. That shared shape is exactly what makes the swap a two-line change. (One detail to keep in mind for your own evaluation: Dijkstra's returned path includes the start node, so its step count is len(path) - 1.)

Resources​