Skip to main content

Lesson 5 · Implementing compute_path()

Module 5 · Dijkstra's Algorithm

Lesson 5 · Implementing compute_path()

60 minPython algorithmPaper trace → code
👩‍🏫

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

This is the heart of Module 5: turning the hand-trace from Lesson 3 into working Python. Every step you did on paper becomes a few lines of code — no new Python concepts, just dictionaries, lists, loops, and in combined into a precise algorithm.

Learning Objectives

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

  • Initialize distances, previous, and visited in code
  • Find the unvisited node with the smallest distance
  • Update a node's neighbors using the graph dictionary
  • Write the main loop with the right stopping condition
  • Reconstruct and reverse the path
Printable knowledge checks — the 5 questions from this lesson on one page, with room to write. Teachers: answer key.

Activity · Implement compute_path​

Five steps, and each one is a line of the paper trace turned into code. Print the distance table after each step and compare it with what you worked out by hand — a wrong number is far easier to find now than at the end.

Step 1 · Set up the three structures​

Every step on paper maps to code. Start by creating the structures — all distances at "infinity" (999999), except the start at 0:

def compute_path(self, destination):
    distances = {}
    previous = {}
    visited = []

    for node in self.graph:
        distances[node] = 999999      # "infinity" — no path found yet

    distances[self.position] = 0       # start is 0 from itself
    previous[self.position] = None     # nothing before the start

Why 999999? It stands in for infinity. Any real path will be shorter, so the first path found to any node always replaces it.

Knowledge Check

Why are all distances initialized to 999999 except the start?

Step 2 · Find the smallest unvisited node​

The core decision: scan every node, skip visited ones, keep the smallest distance seen.

current = None
current_distance = 999999
for node in distances:
    if node not in visited:
        if distances[node] < current_distance:
            current = node
            current_distance = distances[node]

This is a classic "find the minimum" pattern: start with a bad value, look at everything, remember the best. After the loop, current is the closest unvisited node.

Knowledge Check

What does this loop leave in the variable current?

Step 3 · Update neighbors, then mark visited​

For each unvisited neighbor, offer a distance of distances[current] + 1; keep it only if it's shorter than what the neighbor already had:

for neighbor in self.graph[current]:
    if neighbor not in visited:
        new_distance = distances[current] + 1
        if new_distance < distances[neighbor]:
            distances[neighbor] = new_distance
            previous[neighbor] = current

visited.append(current)      # done with current — AFTER updating neighbors

The if new_distance < distances[neighbor] check is what keeps the shortest path — if you always updated, a longer route could overwrite a shorter one already found.

Knowledge Check

Why the check `if new_distance < distances[neighbor]` before updating?

Step 4 · The main loop​

Wrap find-minimum and update-neighbors in a loop that runs until the destination is visited — with a safety check for unreachable destinations:

while destination not in visited:
    # find minimum unvisited
    current = None
    current_distance = 999999
    for node in distances:
        if node not in visited and distances[node] < current_distance:
            current = node
            current_distance = distances[node]

    if current is None:            # nothing reachable left
        print(f"No path to {destination}!")
        return []

    # update neighbors
    for neighbor in self.graph[current]:
        if neighbor not in visited:
            new_distance = distances[current] + 1
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                previous[neighbor] = current

    visited.append(current)

The current is None check prevents an infinite loop when the destination is walled off by obstacles.

Knowledge Check

What does the `if current is None` check protect against?

Step 5 · Reconstruct and reverse​

Follow previous backward from the destination, then flip the list:

    path = []
    current = destination
    while current is not None:
        path.append(current)
        current = previous[current]

    path.reverse()
    return path

The returned path includes the start — [(0,0), (0,1), (0,2), (1,2), (2,2)] — so the number of steps is len(path) - 1. Run your code on the exact grids you traced in Lesson 3; the output should match your hand traces line for line. And on a clear grid, Dijkstra's step count matches Manhattan's.

Knowledge Check

compute_path returns [(0,0), (0,1), (0,2), (1,2), (2,2)]. How many steps is that?

Real-world connections​

This exact pattern — explore, relax distances, reconstruct — underlies real systems:

Maps

Route engines

Production routing uses faster cousins of this loop (A*, priority queues) on the same idea.

Networks

Link-state routing

Internet routers run Dijkstra-based algorithms to build their forwarding tables.

Logistics

Delivery planning

Shortest-path search plans routes for delivery fleets across road networks.

Wrap-up​

  • What do the three structures hold in code? (Shortest distances, predecessors, finished nodes.)
  • Why check if new_distance < distances[neighbor]? (To keep the shortest path.)
  • Why reverse the reconstructed path, and how many steps is a path of N nodes? (It's built backward; N − 1 steps.)

Resources​