Volume 3 Python, from the metal up · algorithms in the wild · 2

wild·2The algorithms that run the map

Ask your phone for directions and the blue line appears before your thumb has left the screen. Nothing tried every route — there was no time to. This page opens the lid on the algorithms that navigate for you: the one that grows a frontier of settled shortest-distances outward from where you stand, the one that gives that frontier a compass so a game character can flow around a wall, the one that orders tasks when some must come before others, and the one that connects every village to the internet with the least total cable. They are one family. Each takes a graph — corners and roads, courses and prerequisites, villages and links — and extracts a guarantee from it: the cheapest path, a legal order, the minimum wiring. Every number on this page came out of a real run on Python 3.12.7, including the ones where a plausible shortcut quietly returns the wrong answer. Those are the ones to sit with.

iolinked · in the wild · 2 — the checkpoints4 steps

$ algorithms covered in the algorithms that run the map —

›01Dijkstra — the blue route line

›02A* — the route line with a compass

›03Topological sort — what must come first

›04Kruskal's MST — cable to every village

01The blue line that knows the traffic

★ ON THE MAP · dijkstrathe route that was never searched for, only grown

You type a destination and the map answers in milliseconds, across a road network with millions of corners. Hold that in your hand for a second, because the obvious explanation is impossible: it did not try every route. The number of routes through a city is beyond astronomical — no machine finishes that enumeration. Something stranger happened. Starting from you, it grew a frontier of certainty: a set of corners whose true shortest distance is already settled beyond argument, expanding outward not in all directions equally but always through the cheapest edge of the known. Corners join the settled set one at a time, cheapest first, and the moment your destination joins it, the answer is not a guess — it is proven, and everything beyond it was simply never visited.

the blue route line, instantly→dijkstra(roads, you) — one source, every distance

“this corner is 7 minutes away, full stop”→the settled set — stamped final, never reopened

“9 minutes so far — unless something better turns up”→a tentative distance — best-so-far, always allowed to fall

“whichever looks cheapest, next” without scanning→heapq — Chapter 58's heap, doing its day job

the ripple you already know, taught to read price tags→Chapter 44's BFS — Dijkstra is BFS where edges cost money

pin it: The map does not find your route. It proves distances outward from you, cheapest first, and your route is what the proof happens to pass through.

Start from what you already own. Chapter 44's breadth-first search explores a graph in rings: everything one hop away, then two hops, then three. That is a correct shortest-path algorithm under one assumption so quiet you may not have noticed making it — that every edge costs the same. Roads do not. A motorway hop and a back-alley hop are both “one edge”, and the moment edges carry weights, hop-count rings stop meaning anything. The question BFS answered — fewest edges — is no longer the question. The question is cheapest total cost, and the fix, worked out by Edsger Dijkstra in 1956 — in about twenty minutes, over coffee, by his own cheerful account — is to keep BFS's shape and change what the ring is made of: expand not by hops, but by accumulated cost.

The machinery is two numbers per corner and one rule. Every corner carries a tentative distance: the cost of the best route found so far, which is honest bookkeeping, not a commitment — it is allowed to fall whenever a better road arrives. That falling has a name, relaxation, and you will watch it happen in the widget: corner C first sighted at 7 via the direct road, then revised down to 5 when a route through B turns out cheaper. The rule is the algorithm: among all corners not yet settled, take the one with the smallest tentative distance, stamp that number as final, and relax its neighbours. That is everything. The loop does it seven times on our seven-corner map and the settled stamps come out in cost order: A(0) B(2) C(5) D(7) E(9) F(10) G(12).

The step that deserves suspicion is the stamp. How can we declare 7 final for corner D while whole regions of the map are still unexplored — could some undiscovered route not undercut it? Walk the escape routes: any other route to D starts inside the settled set and must leave it through some frontier corner. But D was chosen as the cheapest frontier corner — every other exit already costs at least 7 before the route has even finished — and roads only ever add cost from there. The undiscovered route is dead before it draws breath. Notice the load-bearing phrase: roads only ever add. The proof spends that assumption silently, and the run at the bottom of this section shows you exactly what breaks when a road pays you to drive it.

One Python honesty before you step it: the textbook algorithm wants to decrease a corner's key inside the priority queue, and Chapter 58's heapq has no cheap way to do that. The working idiom does not bother. When a distance improves, push a second entry and leave the stale one where it lies; whenever a pop comes up worth more than the distance on record, it is a ghost — skip it. Our run pops 10 entries for 7 corners and skips 3 ghosts. Watch for them.

Run the same seven corners for real and the trace reads like the widget: three REVISED lines — C's 7 falling to 5, D's 8 falling to 7, G's 15 falling to 12 — and three stale ghosts skipped on the way out. Then the second half of the run hands the same function a road with a negative cost, and the invariant this whole section is built on fails in plain sight: corner A gets settled at 2, and then gets settled again at 1. “Settled” stopped meaning anything.

RUN · the frontier, growingseven corners, three revisions, three ghosts — then a negative road breaks the stamp

you type
$ python dijkstra.py

import heapq

ROADS = {
    "A": [("B", 2), ("C", 7)],
    "B": [("A", 2), ("C", 3), ("D", 6)],
    "C": [("A", 7), ("B", 3), ("D", 2), ("E", 4)],
    "D": [("B", 6), ("C", 2), ("F", 3)],
    "E": [("C", 4), ("F", 5), ("G", 6)],
    "F": [("D", 3), ("E", 5), ("G", 2)],
    "G": [("E", 6), ("F", 2)],
}


def dijkstra(graph, start, trace=False):
    dist = {start: 0}
    settled, pops, skips = [], 0, 0
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        pops += 1
        if d > dist[u]:                       # a stale entry - skip it
            skips += 1
            if trace:
                print("  pop %s at %d  -> stale (already settled at %d), skip"
                      % (u, d, dist[u]))
            continue
        settled.append(u)
        if trace:
            print("  pop %s at %d  -> SETTLED" % (u, d))
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                if trace and v in dist:
                    print("      relax %s: %d beats %d  -> REVISED, push (%d, %s)"
                          % (v, nd, dist[v], nd, v))
                elif trace:
                    print("      relax %s: first sighting at %d, push (%d, %s)"
                          % (v, nd, nd, v))
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist, settled, pops, skips


print("the road network: 7 corners, 10 roads, cost = minutes")
dist, settled, pops, skips = dijkstra(ROADS, "A", trace=True)
print()
print("settled order :", "  ".join("%s(%d)" % (u, dist[u]) for u in settled))
print("final distances:", dist)
print("heap pops: %d   settled: %d   stale skips: %d" % (pops, len(settled), skips))

print()
print("now hand it a negative road: S->A 2, S->B 5, B->A -4  (correct A = 1)")
NEG = {"S": [("A", 2), ("B", 5)], "A": [], "B": [("A", -4)]}
dist2, settled2, pops2, skips2 = dijkstra(NEG, "S", trace=True)
print("settled order :", "  ".join(settled2))
print("final distances:", dist2)

you see
the road network: 7 corners, 10 roads, cost = minutes
  pop A at 0  -> SETTLED
      relax B: first sighting at 2, push (2, B)
      relax C: first sighting at 7, push (7, C)
  pop B at 2  -> SETTLED
      relax C: 5 beats 7  -> REVISED, push (5, C)
      relax D: first sighting at 8, push (8, D)
  pop C at 5  -> SETTLED
      relax D: 7 beats 8  -> REVISED, push (7, D)
      relax E: first sighting at 9, push (9, E)
  pop C at 7  -> stale (already settled at 5), skip
  pop D at 7  -> SETTLED
      relax F: first sighting at 10, push (10, F)
  pop D at 8  -> stale (already settled at 7), skip
  pop E at 9  -> SETTLED
      relax G: first sighting at 15, push (15, G)
  pop F at 10  -> SETTLED
      relax G: 12 beats 15  -> REVISED, push (12, G)
  pop G at 12  -> SETTLED
  pop G at 15  -> stale (already settled at 12), skip

settled order : A(0)  B(2)  C(5)  D(7)  E(9)  F(10)  G(12)
final distances: {'A': 0, 'B': 2, 'C': 5, 'D': 7, 'E': 9, 'F': 10, 'G': 12}
heap pops: 10   settled: 7   stale skips: 3

now hand it a negative road: S->A 2, S->B 5, B->A -4  (correct A = 1)
  pop S at 0  -> SETTLED
      relax A: first sighting at 2, push (2, A)
      relax B: first sighting at 5, push (5, B)
  pop A at 2  -> SETTLED
  pop B at 5  -> SETTLED
      relax A: 1 beats 2  -> REVISED, push (1, A)
  pop A at 1  -> SETTLED
settled order : S  A  B  A
final distances: {'S': 0, 'A': 1, 'B': 5}

what the run is telling you

The settled order A(0) B(2) C(5) D(7) E(9) F(10) G(12) comes out sorted by distance — not by accident, by construction. The frontier always extends through its cheapest corner, so corners are proven in cost order, the way BFS proves them in hop order.
Three ghosts. C was pushed at 7 and again at 5; when the stale (7, C) finally surfaced, one comparison — 7 > dist[C] — identified and discarded it. That comparison is the entire price Python pays for heapq having no decrease-key. 10 pops for 7 corners, and the asymptotics do not move.
The negative road is not a bigger example, it is a broken axiom. Look at the last trace: settled order : S A B A. A was stamped final at 2, and the stamp was a lie — the route through B undercut it afterwards, exactly what the proof said could never happen while roads only add cost.
This lazy variant limps to the right number by re-settling A. Do not be comforted: that recovery is not guaranteed cheap — on adversarial graphs the re-settling cascades exponentially — and the classic variant with a visited set simply returns the wrong distance and says nothing. The algorithm for graphs where edges can pay you back is Bellman-Ford, which plans for revision instead of forbidding it — that is all we will say about it here.

Where the simple story ends

It is fair to say the map is doing this in spirit: growing certainty outward, cheapest first, never reopening what is proven. It is not fair to say your phone runs this exact loop over raw corners — at continental scale the real systems precompute shortcut hierarchies so that most of the graph is never touched at query time. What survives at every scale is the invariant you just stepped: a settled distance is final because roads only add cost — the precomputation is built on that same proof, applied earlier.

reach for it when

One starting point, many possible destinations, and every step has a non-negative price — cheapest route, cheapest sequence of moves, cheapest anything where costs accumulate and never refund.

Dijkstra proves distances in every direction, including away from where you are going. Give it a compass →

02How game characters walk around walls

★ ON THE MAP · a-starclick a spot across the map; the character is already moving

In any strategy game, click a point on the far side of a wall and the character does not hesitate, does not wander, does not press its face into the obstacle like a robot vacuum. It flows around — instantly, and along the shortest way. The game is solving Dijkstra's problem, but it holds one extra card that Dijkstra never uses: it knows where you clicked. Dijkstra proves distances in every direction, including directly away from the goal, because it has no idea which direction matters. Give the search an honest estimate of the distance remaining — on a grid, just count the rows and columns left — and the circle of exploration collapses into a beam pointed at your click. That is A*: distance so far, plus an honest guess of distance to go, and the guess is only allowed to flatter, never to exaggerate.

the click — a destination the search is told about→GOAL — the one input Dijkstra ignores

“I have walked 4 cells to get here”→g — exact, paid for, past tense

“it is at least 6 more, ignoring walls”→h = manhattan — a promise never to overestimate

who gets expanded next→the heap, ordered by f = g + h instead of g

delete the compass and watch the beam widen to a circle→h = 0 — A* degenerates into exactly Dijkstra

pin it: A* is Dijkstra with a compass. The compass may flatter the remaining distance but never exaggerate it — and h = 0 is the flattery taken to its limit, which is why Dijkstra is just A* with nothing to say.

Watch section 01's frontier once more and the waste is almost painful. The ripple spreads behind the start, into corners that no sane route to the goal could ever use, and it must — with no information about where the goal is, every cheap corner might matter. A* is what happens when you stop withholding the one fact you had all along. Rank the frontier not by g, the exact cost paid so far, but by f = g + h, where h estimates the cost still to come. A cell two steps behind the start now carries g = 2 plus an h that grew by two as well — its f is hopeless, and the heap simply never gets around to it. The frontier stops being a circle and becomes a beam.

Everything hangs on the quality of the guess, and here is the part to memorise: the guess is allowed to be wrong in one direction only. An admissible heuristic never overestimates the true remaining cost. Why that direction? Because A* stops when the goal is settled, and the safety argument is Dijkstra's argument wearing a compass: when the goal surfaces with cost f, every other frontier entry carries f' = g' + h' at least as large — and since h' promised to be at most the true remaining cost, the true cost of finishing any of those routes is at least f' too. No hidden bargain survives. Flip the direction — let h exaggerate just once — and that sentence dies: a frontier route can look expensive while actually being cheap, the search discards it, and returns a confident wrong answer. On a grid where you move one cell at a time, Manhattan distance — rows remaining plus columns remaining — is admissible for free, because it is the cost in a world with no walls, and adding walls only ever makes things worse.

The widget below runs both searches on the same field: a 6×10 courtyard, a wall spur, start and goal on either side. First the ripple with h = 0 — count the cells it touches, especially the ones behind the start. Then the beam with Manhattan. Same field, same code, same guaranteed-shortest answer of 8 steps; the only change is the sorting key, and the bill drops from 40 cells to 17. Watch what the wall does to the beam, too: the estimate knows nothing about walls, so the beam presses into the pocket, pays for its optimism, spills around the end of the spur, and narrows again. That recovery is not luck — it is the admissibility guarantee absorbing the wall's surprise.

Now the run — and then the temptation. If a compass this honest saves this much, why not exaggerate it a little? Multiply h by ten and the search becomes nearly greedy: it beelines, expands almost nothing, feels wonderful. The second half of the run does exactly that on a field where the straight line crosses mud, and you can watch the swindle in the numbers: 7 cells expanded instead of 17 — and a path costing 16 when the true cheapest is 8. The inflated compass did not find the path faster. It found a different, worse path faster, with total confidence.

RUN · ripple, beam, and a compass that liesboth searches on the walled field, then the inflated heuristic caught mid-swindle

you type
$ python astar.py

import heapq

GRID = ["..........",
        "....#.....",
        "....#.....",
        ".S..#..G..",
        "..........",
        ".........."]
ROWS, COLS = len(GRID), len(GRID[0])


def find(ch):
    for r in range(ROWS):
        for c in range(COLS):
            if GRID[r][c] == ch:
                return (r, c)


START, GOAL = find("S"), find("G")


def neighbours(r, c):
    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < ROWS and 0 <= nc < COLS and GRID[nr][nc] != "#":
            yield nr, nc


def search(h):
    """Dijkstra IS this function with h = zero. A* is this function with a compass."""
    g = {START: 0}
    heap = [(h(*START), 0, START)]
    expanded, order = set(), []
    while heap:
        f, gu, u = heapq.heappop(heap)
        if u in expanded:
            continue
        expanded.add(u)
        order.append(u)
        if u == GOAL:
            return g[GOAL], order
        for v in neighbours(*u):
            ng = gu + 1
            if ng < g.get(v, float("inf")):
                g[v] = ng
                heapq.heappush(heap, (ng + h(*v), ng, v))
    return None, order


def manhattan(r, c):
    return abs(r - GOAL[0]) + abs(c - GOAL[1])


cost_d, order_d = search(lambda r, c: 0)          # no compass: Dijkstra's blind ripple
cost_a, order_a = search(manhattan)               # the honest compass

print("grid %dx%d, wall spur on column 4 rows 1-3, S=%s  G=%s" % (ROWS, COLS, START, GOAL))
print("manhattan says 6; the true path dips under the wall and costs 8")
print()
print("cells expanded, h = 0         (Dijkstra):", len(order_d))
print("cells expanded, h = manhattan (A*)      :", len(order_a))
print("path cost from both: %d = %d  - same answer, well under half the work" % (cost_d, cost_a))


def show(order, label):
    touched = set(order)
    print()
    print(label)
    for r in range(ROWS):
        row = ""
        for c in range(COLS):
            if GRID[r][c] == "#":
                row += " #"
            elif (r, c) == START:
                row += " S"
            elif (r, c) == GOAL:
                row += " G"
            elif (r, c) in touched:
                row += " ."
            else:
                row += "  "
        print(row)


show(order_d, "every cell h=0 expanded (the ripple):")
show(order_a, "every cell manhattan expanded (the beam):")

print()
print("now the dishonest compass: h = 10 * manhattan, on a muddy field")
MUD = ["1111111",
       "1333331",
       "1111111"]          # cost to ENTER each cell; the middle row is mud
M_ROWS, M_COLS = 3, 7
M_START, M_GOAL = (1, 0), (1, 6)


def m_neighbours(r, c):
    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < M_ROWS and 0 <= nc < M_COLS:
            yield nr, nc


def m_search(h):
    g = {M_START: 0}
    heap = [(h(*M_START), 0, M_START)]
    expanded, order = set(), []
    while heap:
        f, gu, u = heapq.heappop(heap)
        if u in expanded:
            continue
        expanded.add(u)
        order.append(u)
        if u == M_GOAL:
            return g[M_GOAL], order
        for v in m_neighbours(*u):
            ng = gu + int(MUD[v[0]][v[1]])
            if ng < g.get(v, float("inf")):
                g[v] = ng
                heapq.heappush(heap, (ng + h(*v), ng, v))
    return None, order


def m_manhattan(r, c):
    return abs(r - M_GOAL[0]) + abs(c - M_GOAL[1])


cost_h, order_h = m_search(m_manhattan)                     # honest: never overestimates
cost_x, order_x = m_search(lambda r, c: 10 * m_manhattan(r, c))  # inflated: lies

print("  going around the mud costs 8; straight through costs 16")
print("  honest h     : path cost %2d, %2d cells expanded" % (cost_h, len(order_h)))
print("  inflated 10*h: path cost %2d, %2d cells expanded  <- faster, and WRONG"
      % (cost_x, len(order_x)))

you see
grid 6x10, wall spur on column 4 rows 1-3, S=(3, 1)  G=(3, 7)
manhattan says 6; the true path dips under the wall and costs 8

cells expanded, h = 0         (Dijkstra): 40
cells expanded, h = manhattan (A*)      : 17
path cost from both: 8 = 8  - same answer, well under half the work

every cell h=0 expanded (the ripple):
 . . . . . . .
 . . . . # .
 . . . . # . .
 . S . . # . . G
 . . . . . . . .
 . . . . . . .

every cell manhattan expanded (the beam):

         #
   . . . #
 . S . . # . . G
   . . . . . . .


now the dishonest compass: h = 10 * manhattan, on a muddy field
  going around the mud costs 8; straight through costs 16
  honest h     : path cost  8, 17 cells expanded
  inflated 10*h: path cost 16,  7 cells expanded  <- faster, and WRONG

the numbers that settle it

40 against 17, same 8-step answer. Read the two maps, not just the counts: the ripple filled the region behind S almost completely; the beam left it nearly untouched. The saving is not cleverness at the goal — it is refusal at the back.
The beam is not a line. Manhattan knows nothing about the wall, so the search pressed into the pocket in front of the spur, paid a few cells there, and flowed around. An honest-but-imperfect compass costs extra expansions, never a wrong answer — that asymmetry is the entire design.
The inflated compass is the measured scandal: 7 cells, and a path costing 16 where 8 exists. Multiplying h by 10 made the mud row's estimate outweigh the detour's reality, so the search never gave the detour a chance. Games actually ship this trade on purpose — weighted A* buys speed with bounded sub-optimality — but it is a decision, made with the eyes open, not a free lunch.
And the degenerate case is worth saying out loud: set h = 0 — an estimate that never overestimates anything — and every line of search is Dijkstra. One function, two names, distinguished only by how much the compass is willing to say.

Where the simple story ends

Real game engines rarely run A* over raw grid cells — they run it over navigation meshes, precomputed polygons that shrink the graph a thousandfold, and at continental scale mapping systems lean on precomputed hierarchies for the same reason. What is fair to say: wherever a character or a route flows around an obstacle toward a known goal, an admissible-estimate search is underneath, and the admissibility rule you just watched fail is the rule those systems are engineered never to break.

reach for it when

Dijkstra's problem plus one known destination — and you can name a cheap estimate of the remaining cost that never overestimates: straight-line distance on maps, Manhattan on grids, zero when you know nothing.

Both of these order corners by a number. The next algorithm orders tasks by something a number cannot express: permission →

03What must come before what

★ ON THE MAP · toposortthe registrar, the build system, and the recipe all run the same loop

You cannot take Data Structures before Intro — the catalogue says so. Algorithms wants both Maths and Data Structures behind you; the final Project wants nearly everything. Nobody hands you a legal order for the whole degree; you get scattered rules of the form this before that, and somehow the registrar publishes a schedule that honours every one of them. The same puzzle wears a dozen uniforms. A build system must compile a library before the things that link against it. A recipe wants the onions chopped before they are fried. A spreadsheet must recompute a cell before the cells that read it. The answer, everywhere, is one loop with a name on it — Kahn's algorithm — and its whole strategy fits in a sentence: repeatedly take anything with no remaining prerequisites, and cross it off everywhere it was needed.

“Intro before Data Structures”, one catalogue rule→an edge Intro → DataSt in a directed graph

how many prerequisites a course still has→indeg[v] — the only number the loop tracks

“free to take right now”→indeg == 0, waiting in Chapter 52's deque

finishing a course unlocks the ones behind it→indeg[v] -= 1 — and at zero, v joins the queue

the catalogue with a circular requirement in it→the queue dries up with courses remaining — deadlock, detected

pin it: Nobody plans the order. The order falls out of counting down prerequisites — and when the count-down stalls with work remaining, that stall IS the proof that no legal order exists.

First, be precise about what kind of object the catalogue is. Courses are nodes; every rule “X before Y” is a directed edge from X to Y. Direction is the entire content — an undirected “these two are related” would say nothing about order — and if the rules are sane, following arrows can never loop back to where you started. That object has a name: a directed acyclic graph, a DAG, and the thing we want from it is a topological order — a line-up of all the nodes in which every arrow points forward. No arrow may reach backwards to a node already behind it. That is the registrar's schedule, the build plan, the recipe sequence, stated as one property.

Kahn's algorithm earns the order without ever looking at the future. Give every node one counter, indegree: how many prerequisites still unfinished. Nodes sitting at zero owe nothing to anyone — they are safe to take right now, so they wait in a ready queue (Chapter 52's collections.deque, since we take from the front and add at the back). The loop is three moves. Take a node from the queue and append it to the order. For each node it pointed at, count that arrow down — one prerequisite of theirs just got done. Any counter that reaches zero joins the queue. Every node is taken once, every edge counted down once: O(V + E), no cleverness, no lookahead, and the order that falls out honours every rule by construction — a node physically cannot be taken while its counter is positive.

The deep part is what happens when the input is poisoned. Add one circular rule — say the Project is somehow required before Data Structures, while Data Structures still leads, through Algorithms, to the Project — and watch the widget's second act. The loop does not crash, does not spin forever, does not emit a half-truth with a warning. It takes the three courses that were still legal, and then the ready queue dries up with three courses remaining — each waiting on another one in the room. That stall is not a failure mode; it is the detector. Nodes left over after the queue empties are exactly the nodes trapped in or behind a cycle, so stuck > 0 is a proof that no legal order exists — the same verdict a build tool prints as “circular dependency detected”, seconds before you find the two config files that import each other.

RUN · the registrar's loop, then the poisoned cataloguesix courses ordered, then one back-edge and the queue runs dry

you type
$ python toposort.py

from collections import deque

COURSES = ["Intro", "Maths", "DataSt", "Databases", "Algos", "Project"]
NEEDS = [("Intro", "DataSt"),        # Intro must come before Data Structures
         ("Intro", "Databases"),
         ("Maths", "Algos"),
         ("DataSt", "Algos"),
         ("DataSt", "Project"),
         ("Databases", "Project"),
         ("Algos", "Project")]


def kahn(nodes, edges, trace=False):
    after = {u: [] for u in nodes}
    indeg = {u: 0 for u in nodes}
    for u, v in edges:
        after[u].append(v)
        indeg[v] += 1
    ready = deque(u for u in nodes if indeg[u] == 0)
    order = []
    if trace:
        print("  indegrees:", dict(indeg))
        print("  ready    :", list(ready))
    while ready:
        u = ready.popleft()          # anything with no remaining prerequisites
        order.append(u)
        for v in after[u]:
            indeg[v] -= 1            # one prerequisite of v just got done
            if indeg[v] == 0:
                ready.append(v)
        if trace:
            print("  take %-9s ready is now %s" % (u, list(ready)))
    stuck = [u for u in nodes if u not in order]
    return order, stuck


print("the prerequisite map: 6 courses, 7 must-come-before rules")
order, stuck = kahn(COURSES, NEEDS, trace=True)
print()
print("one valid order:", " -> ".join(order))
print("stuck:", len(stuck))

print()
print("now poison it: add Project -> DataSt (a project you need before the")
print("course that is needed before the project)")
order2, stuck2 = kahn(COURSES, NEEDS + [("Project", "DataSt")], trace=True)
print()
print("took %d of %d courses, then the ready queue dried up" % (len(order2), len(COURSES)))
print("stuck: %d courses, every one waiting on another in the list: %s"
      % (len(stuck2), stuck2))
print("that is the deadlock detector: stuck > 0 means a cycle, and no order exists")

you see
the prerequisite map: 6 courses, 7 must-come-before rules
  indegrees: {'Intro': 0, 'Maths': 0, 'DataSt': 1, 'Databases': 1, 'Algos': 2, 'Project': 3}
  ready    : ['Intro', 'Maths']
  take Intro     ready is now ['Maths', 'DataSt', 'Databases']
  take Maths     ready is now ['DataSt', 'Databases']
  take DataSt    ready is now ['Databases', 'Algos']
  take Databases ready is now ['Algos']
  take Algos     ready is now ['Project']
  take Project   ready is now []

one valid order: Intro -> Maths -> DataSt -> Databases -> Algos -> Project
stuck: 0

now poison it: add Project -> DataSt (a project you need before the
course that is needed before the project)
  indegrees: {'Intro': 0, 'Maths': 0, 'DataSt': 2, 'Databases': 1, 'Algos': 2, 'Project': 3}
  ready    : ['Intro', 'Maths']
  take Intro     ready is now ['Maths', 'Databases']
  take Maths     ready is now ['Databases']
  take Databases ready is now []

took 3 of 6 courses, then the ready queue dried up
stuck: 3 courses, every one waiting on another in the list: ['DataSt', 'Algos', 'Project']
that is the deadlock detector: stuck > 0 means a cycle, and no order exists

read the queue, not the order

The clean run's schedule — Intro → Maths → DataSt → Databases → Algos → Project — honours all seven rules, and you can audit it in one pass: every arrow in the catalogue points rightward along that line.
It is one valid order, not the valid order. Maths could have gone first; Databases could trade places with DataSt. Whenever the ready queue holds more than one course, the choice among them is free, and every choice leads to a different, equally legal schedule. This loop takes them in arrival order because a deque pops from the front — determinism is a property of the container, not of the problem.
In the poisoned run, look at what one added rule did to the numbers before anything ran: DataSt's indegree became 2. The loop then took Intro, Maths, Databases — all still perfectly legal — and stalled. Three courses, each waiting on another in the same list: DataSt waits on Project, Project waits on Algos, Algos waits on DataSt.
Note that Databases was not stuck, even though it points into the doomed Project. Being upstream of a cycle is survivable; being inside or downstream of one is not. The stuck list is precisely the cycle and everything trapped behind it — which is why build tools can name the guilty files, not just declare failure.

Where the simple story ends

Real schedulers — university registrars, make, package installers — are solving this problem plus constraints this loop ignores: capacity per term, versions, priorities, work that can run in parallel. What they keep is the skeleton you just stepped: a dependency DAG, ready = indegree zero, and the dried-up queue as the cycle alarm. Python ships that skeleton as graphlib.TopologicalSorter, whose prepare() raises CycleError for exactly the reason our stuck list is non-empty.

reach for it when

Tasks constrain each other by order, not by cost — builds, migrations, imports, spreadsheet recalculation — and you need either a legal sequence or a proof that the rules contradict themselves.

Order settled, distances proven. One question left on the map: which connections are worth paying for at all →

04Cable to every village

★ ON THE MAP · kruskal + union-findthe cheapest network that still reaches everyone

Seven villages, one budget, and a promise: every village gets the internet. Between some pairs of villages a cable can be trenched, and each possible link has a price — the terrain decides. You do not need a cable between every pair; you need every village reachable, directly or through neighbours, for the least total money. Joseph Kruskal's 1956 answer sounds too greedy to be safe: price every possible link, then walk the list cheapest-first, laying any cable that connects something new and refusing any cable whose two ends are already connected. No lookahead, no regret, no undo — and it is provably unbeatable. The working heart of it is the refusal, and the refusal is a question you already know how to answer fast: do these two villages already answer to the same root? That is Chapter 61's union-find, and this section is where the strange little forest you built there gets its payoff.

every possible link, priced by the terrain→sorted(links) — cheapest cable first, always

“are these two already connected, even indirectly?”→find(u) == find(v) — Chapter 61's union-find, near-constant time

laying a cable merges two clusters of villages→parent[ry] = rx — one pointer write

the finished network: everyone reachable, no loops→a spanning tree — exactly n - 1 cables for n villages

the bill the council actually signs→total — 23 km here, and no other tree beats it

pin it: Kruskal never plans the network. It just refuses to pay twice for a connection it already owns — and the refusals, not the purchases, are where the optimality lives.

Name the object first. A network that reaches all n villages with no redundant loops is a spanning tree, and a moment's counting tells you every spanning tree has exactly n − 1 edges: each cable after the first must connect one new village, and there are n - 1 villages left to connect. A loop, by the same token, is a cable that connects nothing new — both of its ends were already reachable from each other — so its entire price is waste. The cheapest such tree is the minimum spanning tree, and it is what your problem is secretly shaped like whenever you must connect a set of things pairwise for the least total cost: villages and fibre, circuit pins and copper, sensors and wiring runs. The same greedy skeleton, run in reverse gear, is how single-linkage clustering decides which data points belong together.

So the algorithm needs one fast primitive: given two villages, decide connected already, or not yet? — where “connected” means through any chain of laid cables, not directly. Walking the network to find out would cost more than the cable. Chapter 61 built the answer: keep every cluster of connected villages as a shallow tree of parent pointers; find chases pointers to a cluster's root — its elected name-tag — compressing the path as it climbs so the next climb is shorter; union merges two clusters by pointing one root at the other. With path compression the climb is effectively constant — the true bound grows so slowly that no input you will ever construct pushes it past five. Kruskal is fifteen lines of that plus a sort: lay the cable if union succeeds, refuse it if both ends already answer to the same root.

The part that should bother you is the greed. Cheapest-first with no lookahead — why does that never paint the network into a corner, the way cheapest-first fails for making change or packing bags? Because of a fact about cuts. Split the villages into two camps, any way you like: some cable must cross the divide, and the cheapest crossing cable is always safe to lay — any network avoiding it must cross the divide somewhere pricier, and swapping that crossing for the cheap one only lowers the bill. Kruskal's scan is that argument applied relentlessly: every accepted cable is the cheapest crossing of the divide between “its two clusters” at that moment. Watch the run below refuse A–C at 3 km — the cheapest cable on offer at that moment — because A and C already answer to the same root through 1+2 km of laid cable. Greed with a memory of what it owns.

RUN · eleven candidates, six cables, one billthe whole tender: every acceptance, every refusal, and the root that refused it

you type
$ python kruskal.py

VILLAGES = ["A", "B", "C", "D", "E", "F", "G"]
LINKS = [(1, "A", "B"), (2, "B", "C"), (3, "A", "C"), (3, "B", "D"),
         (4, "C", "D"), (5, "C", "F"), (5, "D", "E"), (6, "E", "F"),
         (7, "F", "G"), (8, "D", "G"), (9, "E", "G")]      # (km of cable, from, to)

# ch61's union-find, 15 lines: parent map, path compression, union-by-root
parent = {v: v for v in VILLAGES}


def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]     # path compression: point at grandparent
        x = parent[x]
    return x


def union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry:
        return False                      # same root: a loop - refuse the cable
    parent[ry] = rx
    return True


taken, rejected, total = [], [], 0
for cost, u, v in sorted(LINKS):          # cheapest cable first, always
    if union(u, v):
        taken.append((cost, u, v))
        total += cost
        print("  %s-%s %dkm  LAID    (%d of %d edges)" % (u, v, cost, len(taken), len(VILLAGES) - 1))
    else:
        rejected.append((cost, u, v))
        print("  %s-%s %dkm  refused - both ends already answer to root %s" % (u, v, cost, find(u)))

print()
print("cables laid :", " ".join("%s-%s(%d)" % (u, v, c) for c, u, v in taken))
print("refused     :", " ".join("%s-%s(%d)" % (u, v, c) for c, u, v in rejected))
print("total cable : %d km for %d villages (%d cables = n - 1, no loops)"
      % (total, len(VILLAGES), len(taken)))

you see
  A-B 1km  LAID    (1 of 6 edges)
  B-C 2km  LAID    (2 of 6 edges)
  A-C 3km  refused - both ends already answer to root A
  B-D 3km  LAID    (3 of 6 edges)
  C-D 4km  refused - both ends already answer to root A
  C-F 5km  LAID    (4 of 6 edges)
  D-E 5km  LAID    (5 of 6 edges)
  E-F 6km  refused - both ends already answer to root A
  F-G 7km  LAID    (6 of 6 edges)
  D-G 8km  refused - both ends already answer to root A
  E-G 9km  refused - both ends already answer to root A

cables laid : A-B(1) B-C(2) B-D(3) C-F(5) D-E(5) F-G(7)
refused     : A-C(3) C-D(4) E-F(6) D-G(8) E-G(9)
total cable : 23 km for 7 villages (6 cables = n - 1, no loops)

what the tender is telling you

Six cables, 23 km, seven villages — and six is not a coincidence, it is n - 1 arriving on schedule. The moment the count hits it, every remaining candidate is guaranteed a refusal; the run checks them anyway so you can watch it happen.
The first refusal is the lesson in miniature. A–C at 3 km was the cheapest cable on the table when it was refused — cheaper than B–D, which was laid one line later. Cheap is not the criterion. Connects something new is the criterion; cheap only decides the order of consideration.
Every refusal line names root A because by then the growing cluster had elected A its name-tag — watch the roots under the villages in the widget converge to it. Five refusals, each one a find answering “same root” in a handful of pointer hops. That answer costing near-constant time is the entire reason the sort, at O(E log E), dominates the bill.
Ties broke by luck of the sort order — at 3 km, A–C happened to be considered before B–D — and with distinct considerations a different tie order can pick different cables. The total cannot move: 23 km is the minimum, and when all prices are distinct the tree itself is unique. Equal prices make the tree non-unique; they never make the bill negotiable.

Where the simple story ends

Kruskal is one of two classical ways in. Prim's algorithm grows a single cluster outward from one village, always adding the cheapest cable that leaves it — section 01's frontier, harvesting cables instead of distances — and arrives at the same 23 km. And real network build-outs answer to constraints this model cannot see: cable capacity, redundancy requirements (a tree has exactly one path between any two points — one backhoe can split it), politics. The MST is where the engineering conversation starts, because it names the cheapest connected baseline that everything else is a deliberate, costed departure from.

reach for it when

You must connect all of a set, pairwise costs given, least total spend — fibre, pipes, circuit traces — or cluster data by cutting the longest links of its cheapest skeleton.

Step back and look at the family portrait, because the four are more alike than their names suggest. Dijkstra and A* rank a frontier by a number — cost paid, or cost paid plus an honest promise — and harvest a guarantee per node. Kahn ranks by a counter hitting zero and harvests a guarantee per rule. Kruskal ranks a bare list by price and harvests a guarantee per refusal. In every one of them the loop is small enough to memorise by accident; what carries the weight is an invariant — settled means final, the estimate never exaggerates, zero means free to take, same root means already paid for — plus the right container from Volume 4 to make maintaining it cheap: the heap, the deque, the parent forest. That is what an algorithm is, seen from the metal up: a promise you can afford to keep on every step. The map in your pocket keeps four of them at once.

Four algorithms that run the map. Next: the ones that run the internet — how a packet finds a route nobody planned, and how a billion pages get ranked →

end of in the wild · 2 · four algorithms

iolinked

designed & developed by Ajai Raj

Python, from the metal up · a product of iolinked