A First Taste of Algorithms · Maps, Mazes, and Networks

The thread: depth-first search

The opposite temperament: instead of expanding evenly, commit. Walk down one corridor as far as it goes; only when stuck, back up to the last junction with an untried option and commit again. This is depth-first search (DFS) — the instinct of every maze-runner in history, including the first one: Greek myth sends Theseus into the Labyrinth trailing Ariadne’s thread, and the thread is the algorithm — it is the record of the current path, paid out going forward, rewound when backing up.

The first person to state the maze method precisely enough to deserve the word algorithm was Charles Trémaux, a French engineer, around 1880 — and his work reached the world in the Récréations Mathématiques of one Édouard Lucas. Yes: the Hanoi man, again, in his other role as mathematics’ great impresario of puzzles. And Lucas’s two appearances in this book are secretly one appearance, because DFS is recursion — Chapter 3 in a new costume. “Explore a vertex” means: mark it visited; for each unseen neighbor, explore that neighbor — a procedure calling itself — and the backing-up is nothing but the call stack unwinding. Ariadne’s thread, Trémaux’s pencil marks, and Chapter 3’s visible staircase are the same object. In the lab you will see it plainly: written iteratively, DFS and BFS differ by one word — serve the line from the back instead of the front, a stack instead of a queue, and the patient ripple becomes the headlong thread.

What DFS does not promise is shortest paths — the thread plunges past near rooms to reach far ones, and Problem 3.1 has you build the maze that proves it. What it does superbly: visit everything reachable, cheaply, while carrying a path in its hand at all times — which makes it the tool of choice when the question is “is there a way at all,” “find me any route,” or, later in your life, a dozen subtler questions about structure.

When hops lie: Dijkstra

BFS’s currency is hops — every edge costs 1. But hallways have lengths, roads have minutes, flights have prices, and the fewest-edges route may be the slowest one. Put a number, a weight, on each edge, and ask for the route of least total weight. Hops now lie; we need a new discipline.

Here it is as a tabletop protocol — play it with coins before reading any code. Every vertex gets a tentative price tag: the start reads 0, all others read ∞ (“no known way yet”). Then repeat:

among vertices not yet settled, pick the one with the cheapest tag and settle it — its tag is now the truth; for each neighbor of the newly settled vertex, check whether traveling through it beats the neighbor’s current tag: settled-tag + edge-weight, and if that is cheaper, write it over the old tag.

That overwrite — “is the path through me better than your best so far?” — is called relaxing an edge, and the whole algorithm is just: settle the cheapest, relax its edges, repeat until done. Run it by hand on this map (it reappears in the lab; distances are minutes):

Home–Park 2, Park–School 5, Home–School 9, School–Library 1, Park–Library 9, Library–Café 4, School–Café 7, Park–Gym 11, Gym–Café 3.

From Home: Park settles at 2; School at 7 — through the park, beating the direct 9; Library at 8 (through School, beating Park’s 11); Café at 12 (through Library, beating School’s 14); Gym at 13 (through Park, beating Café’s 15). Every single answer is a detour beating a direct claim, which is the algorithm earning its keep: the cheap-looking edge is not the cheap path, and only patient relaxation finds out.

Figure 5.3 — The town, then Dijkstra’s settled tags: the red tree is the cheapest-routes answer, and every tag beats a direct edge.

Now name what you just did. Repeatedly commit to the cheapest-looking option. This is Chapter 2’s instinct — Dijkstra’s algorithm is a greedy algorithm — and after Sevenia you are right to demand the theorem before trusting it. It exists, and it is the stays-ahead argument in new clothes: when the cheapest unsettled vertex v is settled at price p, no future discovery can undercut it, because any other route to v must exit the settled region somewhere, and its first step outside already costs at least p — v was the cheapest exit, and edges only add. Read that twice; the deep water writes it carefully, and shows the one assumption it leans its whole weight on: edges only add — weights are not negative. Hand the argument a negative edge and it collapses like greedy in Sevenia, with a three-vertex counterexample waiting in Problem 3.3.

A human moment

In 1956, Edsger Dijkstra — twenty-six, employed as the Netherlands’ first professional “programmer,” a job title so new his marriage license wouldn’t accept it — was shopping in Amsterdam with his fiancée. Tired, they sat on a café terrace, and in about twenty minutes, over coffee, without pencil or paper, he designed the algorithm you just executed with coins. The constraint was the method, he later said: designing without paper “you are almost forced to avoid all avoidable complexities.” He thought so little of the result that he didn’t publish for three years, and then only as a three-page note. That note now guides essentially every navigation app on Earth; some appreciable fraction of all routed packets, delivered parcels, and turned-left cars are downstream of one tired afternoon. Two lessons, both real: simplicity is a discipline, not an accident — and the inventor is reliably the worst judge of which twenty minutes mattered.

Deeper water: why the cheapest exit is safe

The invariant: every settled vertex’s tag equals its true shortest distance. True at the start (Home, tag 0). Preserved: suppose it holds, and v is the cheapest unsettled tag, value p, about to settle. Any path from the start to v begins inside the settled region and at some point crosses out — let its first unsettled vertex be u. The path’s length up to u is a true settled distance plus one relaxed edge, which is exactly what u’s tag records or better, so the path already costs ≥ tag(u) ≥ tag(v) = p by v’s minimality — and the remaining leg from u onward cannot bring the total back down, because the remaining edges only add. So no path to v beats p; settling is safe. Decisive at the end: all settled, all true. ∎ (Fifth appearance of the trick.)

The italicized clause is the load-bearing one. With a negative edge, “remaining edges only add” is false and the proof dies at that exact word — and so does the algorithm, as your three-vertex counterexample will show. A theorem’s hypotheses are not decoration; they are the places it can be killed.

One honesty note on cost: our protocol finds the cheapest unsettled vertex by scanning everyone, so a map with n places and m roads costs about n² — fine for towns, sloppy for continents. Real implementations keep the tags in a structure that surrenders its minimum quickly (a heap); the algorithm is unchanged, only the line-keeping improves. Chapter 6 is entirely about what good line-keeping is worth.

Where this leaves us

One abstraction — keep the connections, burn the geography — and three disciplines for walking it. The ripple (a queue): shortest paths in hops, and certified absence when the ripple dies. The thread (a stack, or Chapter 3’s recursion undisguised): any path, all of reachability, cheaply. The price tags (greedy, with a theorem): cheapest paths under honest, nonnegative weights. Between them sits one of the quietest facts in the chapter: BFS and DFS are one word apart. Which end of the line you serve — that is the entire difference between the patient cartographer and the plunging maze-runner. Small hinges; large doors.

You now hold the book’s first half: two questions, two strategies (greedy and the table), recursion beneath both, and the territory — graphs — where they all live. Before Chapter 6 takes up the toll booth this book has been promising since Chapter 1 (sorting: its price, and the astonishing proof that the price has a floor), there is a short interlude. It concerns a rumor you have heard all your life — that computers got fast — and the half of the story the rumor leaves out: most of the speed, measured honestly, was never in the machines. It was in chapters like the five you have just read.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses