05 · The Algorithmic Path

THE SHORTEST PATH — A History of the Art and Science of Problem-Solving

Amsterdam, a café terrace, 1956

Edsger Dijkstra was twenty-six, shopping with his fiancée Ria, and tired. He had recently taken a job at the Mathematisch Centrum in Amsterdam demonstrating a new computer called the ARMAC, and he wanted a problem simple enough to explain to a nontechnical audience yet impressive enough to show the machine earning its keep. Sitting down for coffee, without pencil, paper, or access to a library, he set himself the question of the shortest route between two Dutch cities and, in his own later telling, worked out the solution in about twenty minutes (David Gries, "Edsger Dijkstra and the Shortest-Path Algorithm," Cornell CS). The algorithm he sketched that morning — grow a set of cities whose shortest distance from the start is already known for certain, and at each step add whichever unvisited city is now closest — is still, seven decades later, the default answer whenever a computer needs to find the cheapest way from here to there. He did not publish it until three years afterward, as a spare three-page note that solved two unrelated graph problems in the space most papers need for an abstract (Dijkstra, "A Note on Two Problems in Connexion with Graphs," Numerische Mathematik 1 (1959)).

There is a pleasing, almost too-neat symmetry in the fact that a book called The Shortest Path arrives, in its fifth chapter, at an algorithm literally named for finding shortest paths, invented over coffee in less time than it takes to read this paragraph twice. But the neatness is real, not manufactured, and it marks the hinge this chapter turns on. Chapter 04 showed a generation of scientists discovering that real-world problems — convoys, diets, factories — could be captured as mathematical objects and solved by general-purpose procedures. This chapter is about what happened next: those procedures themselves became objects of study. People began asking not just "does a method exist?" but "how good a method can exist, and how would we know?" Search — the raw, brute business of trying paths through a space of possibilities — became a subject with its own theory, its own proofs, and eventually its own machines.

The Man Whose Name Became a Word

The word for what Dijkstra did that morning — devise a step-by-step procedure guaranteed to reach a correct answer — is algorithm, and the word has its own long detour before it lands in a computer science course.

It comes from the Latinized name of a ninth-century scholar working in the House of Wisdom in Baghdad: Muhammad ibn Musa al-Khwarizmi. His treatise on Hindu-Arabic numerals, translated into Latin as Algoritmi de numero Indorum, gave medieval Europe both a new way to calculate — the positional decimal system, replacing Roman numerals — and, eventually, a new word: algorismus, referring at first specifically to arithmetic done this new way. Only much later, in the twentieth century, did "algorithm" widen into its modern sense: any finite, unambiguous, mechanically executable procedure for solving a class of problems (findanexpert.unimelb.edu.au, "Why are algorithms called algorithms?"; NPR, "How 'algorithm' got its name from a 9th-century Persian mathematician"). Al-Khwarizmi's other great book gave mathematics the word algebra, from al-jabr, "completion" or "restoration" — a term for the operation of moving a quantity from one side of an equation to the other. The scribes of chapter 01 wrote down individual solved problems as teaching examples; al-Khwarizmi wrote down the procedure itself, stripped of any particular numbers, so that it could be applied to numbers no one had thought of yet. That abstraction — the method as an object in its own right, portable across every instance of a problem — is the direct ancestor of everything in this chapter.

The Primitive Moves: Sweeping Outward, Plunging Deep

Before Dijkstra's algorithm, and underneath it, sit two even more basic strategies for exploring a space of possibilities, and it is worth naming them plainly because everything more sophisticated in this chapter is built from them.

Imagine a maze, or a family tree, or a web of friendships, represented the way chapter 02 taught Euler to represent Königsberg: as a graph of nodes and connecting edges. Breadth-first search starts at one node and explores outward in expanding rings — first everything one step away, then everything two steps away, and so on — guaranteeing that the first time it reaches any given node, it has found the shortest possible route to it, measured in number of steps. It was reinvented for exactly this purpose in 1959 by Edward F. Moore, who wanted a mechanical way to find the shortest way out of a maze, though a similar idea had been buried, unpublished, in Konrad Zuse's rejected 1945 doctoral thesis (Wikipedia, "Breadth-first search"). Depth-first search, by contrast, commits to a single path and follows it as far as it can go before backing up — plunging down one corridor of the maze to its very end before trying another. It has no built-in guarantee of finding the shortest route, but it uses far less memory to run and, in the hands of Robert Tarjan and John Hopcroft in the early 1970s, turned out to unlock efficient solutions to a surprising range of graph problems, from testing whether a map can be drawn without crossing lines to finding a network's structural weak points (Wikipedia, "Depth-first search").

Neither strategy knows anything about the problem it is solving beyond the bare shape of the graph. That ignorance is their strength — they work on any graph whatsoever — and their weakness: they waste enormous effort exploring directions that, to anyone who actually understood the problem, would look obviously hopeless. Dijkstra's algorithm is breadth-first search's more disciplined cousin, expanding outward not ring by ring but always toward whichever unvisited node is currently cheapest to reach — which is why it finds not just a short path but provably the shortest one, for any graph where distances are never negative.

A Mouse Named Theseus

Six years before Dijkstra's coffee, at Bell Labs in 1950, Claude Shannon — already famous for founding information theory — built a smaller, stranger monument to the same idea: a maze-solving mechanical mouse he named Theseus, after the hero who navigated the Minotaur's labyrinth by unspooling a thread behind him.

Theseus was, mechanically, a magnet wrapped in a metal shell, dragged along underneath a re-configurable five-by-five maze by an electromagnet hidden beneath the floor, itself driven by a bank of telephone relays functioning as memory. Released into an unfamiliar maze, the mouse would blunder forward, bumping walls, backing up, trying again — a physical enactment of depth-first search with backtracking — until it stumbled onto a hidden slice of "cheese" that closed an electrical contact. But every turn it made was recorded in the relay memory as it went. Reset to the start of the same maze, Theseus would now glide directly to the goal without a single wrong turn, having converted its earlier blind search into a stored, reusable solution (cyberneticzoo.com, "1952 – 'Theseus' Maze-Solving Mouse – Claude Shannon"). This is worth pausing on, because it is a genuinely early and genuinely physical demonstration of the idea that would come to define machine intelligence: search followed by memory is learning. The first pass through a space costs the full price of exploring it. Every later pass can spend that stored knowledge instead of paying again — the same insight, in miniature and in copper wire, that would let Bellman's dynamic programming (chapter 04) avoid resolving identical sub-problems, and that lets a chess program in chapter 10 remember a position it has already evaluated.

Optimism That Never Lies

Dijkstra's algorithm is exhaustive within its expanding frontier — it never skips a node that might turn out to matter — and that thoroughness is also its limit. On a graph with millions of nodes, exploring "everything closer than the current best" before considering anything farther away wastes effort in every direction that has nothing to do with where you are actually trying to go.

The fix arrived in 1968 from a robotics project at the Stanford Research Institute, where researchers Peter Hart, Nils Nilsson, and Bertram Raphael were trying to give a mobile robot named Shakey — one of the first machines able to reason about its own actions in a real room — a way to plan efficient routes around obstacles without exploring the entire building's floor plan every time (Engineering and Technology History Wiki, "Milestones: SHAKEY: The World's First Mobile Intelligent Robot, 1972"). Their algorithm, which came to be called A* (pronounced "A-star"), adds one ingredient to Dijkstra's method: at each step, instead of ranking unexplored nodes purely by the distance already traveled to reach them, A* ranks them by that distance plus a guess — a heuristic estimate of how much farther the goal must still be. On a road map, the straight-line, "as the crow flies" distance to the destination is a natural guess: it is easy to compute and it can never overestimate the true remaining driving distance, since no road is ever shorter than a straight line between the same two points.

That last property — never overestimating — is the entire secret, and it is worth explaining in plain terms because it is one of the most beautiful small theorems in this book's whole story. A heuristic with this property is called admissible: it may be wrong, but it is never wrong in the optimistic direction beyond the truth — it can underestimate the remaining distance, but it can never claim a path is shorter than it actually is. Give A* an admissible heuristic, however crude, and it is mathematically guaranteed to still find the truly shortest path, exactly as Dijkstra's algorithm would, while typically exploring only a sliver of the space Dijkstra's algorithm would have to touch. The heuristic doesn't need to be right. It only needs to never lie in the direction of false hope. Optimism, bounded so it can never overshoot the truth, turns out to be free — you get to search faster and you are never fooled into a wrong answer. Hart, Nilsson, and Raphael's original 1968 paper, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths in Graphs," struggled to find a journal willing to publish it, and Raphael, frustrated, eventually helped found a new AI journal partly so the paper would have somewhere to appear (IEEE Transactions on Systems Science and Cybernetics 4, no. 2 (1968); doi 10.1109/TSSC.1968.300136). A* now runs, in one variant or another, inside video game pathfinding, logistics routing, and the descendants of Shakey still driving across the surface of Mars.

Machines That Prove Theorems

While Shannon's mouse learned mazes and Dijkstra timed his coffee, a separate group at the RAND Corporation was attempting something that, in 1955, sounded closer to science fiction than engineering: teaching a machine to do mathematics.

Allen Newell, Herbert Simon, and the programmer Cliff Shaw set out to build a program that could prove theorems in formal logic — specifically, theorems from Principia Mathematica, the monumental three-volume attempt by Alfred North Whitehead and Bertrand Russell to derive all of mathematics from a small set of logical axioms. Their program, the Logic Theorist, represented each logical statement as a tree-shaped data structure and searched through chains of substitution, detachment, and inference rules — the same problem-space idea chapter 00 traces to Newell and Simon's later theoretical work — hunting for a sequence of legal steps connecting the axioms to the theorem to be proved. Because the space of possible deductions explodes combinatorially with every added step, Newell and Simon needed a way to prune obviously unpromising branches, and borrowed a word for the rules of thumb they used to do it: heuristics, a term Newell had encountered in George Pólya's How to Solve It, the handbook chapter 03 covers in full (Wikipedia, "Logic Theorist").

Completed in 1956, the Logic Theorist went on to prove 38 of the first 52 theorems in Chapter 2 of Principia Mathematica — and, in one case, found a proof more elegant than the one Whitehead and Russell had labored over by hand. The theorem is commonly cited by the number 2.85, although a documented note on Wikipedia's account points out that in the original 1910 and 1963 Cambridge editions of Principia the same theorem is actually numbered 2.53 — a small numbering discrepancy in the popular retelling worth flagging exactly because this book asks its readers to distrust anecdotes that have been smoothed in the retelling. What is well attested is Russell's reaction: Simon showed him the machine's shorter proof, and Russell reportedly responded with delight. The two men then tried to publish the new proof in The Journal of Symbolic Logic, only to have it rejected on the grounds that a new proof of an elementary theorem was not a notable result — the reviewers apparently missing, or unmoved by, the fact that one of the "authors" credited was a computer program (Wikipedia, "Logic Theorist").

Newell, Simon, and Shaw followed the Logic Theorist with a more ambitious successor between 1957 and 1959: the General Problem Solver, or GPS, intended not merely to prove logic theorems but to tackle any problem expressible as a set of states and legal operators — the general problem-space formalism this book leans on throughout. GPS's central technique, means-ends analysis, is simple to state and turned out to be extraordinarily durable: compare your current state to your goal state, identify the single biggest difference between them, and select whichever available operator is known to reduce differences of exactly that kind. Solve the biggest gap first, then repeat on whatever gap remains. It is, in miniature, a general-purpose engine for narrowing an enormous space one deliberate step at a time, rather than wandering it at random (Wikipedia, "General Problem Solver"; Wikipedia, "Means–ends analysis"). GPS eventually ran into the same wall every general method runs into — later chapters, especially 06, will explain why generality and efficiency pull in opposite directions — but the technique it introduced still shows up, essentially unchanged, inside modern automated planning systems.

Five Bets About the Shape of the Space

Step back from any single algorithm in this chapter and a shared logic becomes visible: every search strategy is, underneath its details, a bet about what kind of space it is searching. Naming the bets explicitly turns them from a grab-bag of tricks into a genuine toolkit, one you can hold up against a new problem and ask which bet fits.

Greedy algorithms bet that making the locally best choice at every step, without ever reconsidering it, will add up to a globally good result. This is a dangerous bet — it is easy to construct problems where it fails outright — but when a problem's structure guarantees the bet pays off (a property mathematicians call the matroid or exchange condition in the cleanest cases), greedy strategies are unbeatable for their simplicity and speed. Dijkstra's algorithm is, in this light, a greedy algorithm that happens to be provably safe: always finalize whichever unvisited node is currently cheapest, and never look back.

Divide-and-conquer bets that a hard problem can be split into smaller, structurally identical copies of itself, solved independently, and stitched back together. It is the strategy behind fast sorting and multiplication algorithms, and its bet is about decomposability: does solving the pieces really tell you how to solve the whole?

Dynamic programming, which chapter 04 introduced through Bellman's principle of optimality, bets that a problem's sub-problems overlap — that the same smaller question will recur many times inside a larger search — and that storing each answer the first time it is computed will save enormous repeated effort later. Where divide-and-conquer's pieces are independent, dynamic programming's pieces share work, and the technique exists precisely to avoid redoing that shared work, the way Shannon's mouse never re-explored a corridor it had already mapped.

Backtracking bets that a space can be searched depth-first, provided the search can recognize a dead end early and retreat before wasting further effort down it — the disciplined version of what Theseus did by trial, bump, and correction.

Branch-and-bound, formalized in 1960 by Ailsa Land and Alison Doig for problems requiring whole-number rather than fractional solutions, bets that you can compute a cheap bound on how good any solution branching from a given partial choice could possibly be — and use that bound to prune away entire branches of the search tree without ever visiting them, the instant the bound proves they cannot beat a solution you already have in hand (Wikipedia, "Branch and bound"). It is A*'s admissible heuristic, generalized from finding paths on a map to finding optimal points in a much wider variety of combinatorial spaces.

Five bets, five different guesses about the hidden shape of a problem space. None of them is "the" right way to search; each is the right way when its bet about the space happens to be true. Reading a new problem well enough to know which bet applies is, itself, most of the skill this book is trying to name.

An Algorithm Is a Heuristic That Earned a Proof

There is a temptation, looking backward from a world of route planners and chess engines, to treat "algorithm" and "heuristic" as opposites — one rigorous and guaranteed, the other a rough guess that might fail. The history in this chapter argues for a different picture. Dijkstra's algorithm began as an informal insight about which city to visit next; what made it an algorithm, rather than a hunch, was that Dijkstra could prove the insight always worked. A*'s heuristic estimate is explicitly, by name, a guess — yet paired with the single provable property of admissibility, that guess becomes part of an algorithm with an ironclad optimality guarantee. Newell and Simon's "rules of thumb" for pruning theorem-proving searches were heuristics in the older, looser sense: useful, unproven, sometimes wrong. The field's entire maturation across this chapter is the slow conversion of hunches into guarantees — not by abandoning intuition, but by discovering exactly which intuitions can be proven never to betray you.

This is also where the algorithmic tradition begins to separate from the operations-research tradition of chapter 04. Linear programming and dynamic programming solve well-defined numerical optimization problems. The algorithms in this chapter solve search problems over discrete, often combinatorial spaces — mazes, graphs, logical proofs, game positions — and their central discovery is that the structure of the space itself (its distances, its overlapping sub-problems, its decomposability) determines which search strategy can be proven correct and fast. That discovery sets up the next and darker discovery, waiting in chapter 06: some spaces have no exploitable structure of this kind at all, and no amount of cleverness can manufacture one where none exists.

The Move

Move 05 — Order the search: exploit structure so good paths come first.

• Name which of the five bets fits your space before searching it. Overlapping sub-problems call for dynamic programming; decomposable ones call for divide-and-conquer; a provably safe local choice calls for greedy; anything else usually calls for backtracking or branch-and-bound. Guessing the wrong bet wastes the search before it starts.
• When you must guess, guess optimistically but never past the truth. A* shows that an estimate need not be accurate to be useful — it only needs to be admissible. An honest lower bound on remaining effort is worth more than an unreliable "best guess."
• Remember what you have already searched. Shannon's mouse and Bellman's functional equations share one lesson: the first pass through a space is allowed to be expensive, provided nothing forces you to pay for the same sub-problem twice.
• Distinguish a real guarantee from a plausible heuristic, and say out loud which one you're relying on. The Logic Theorist's "rules of thumb" and Dijkstra's proven-optimal frontier are both search strategies — only one of them promises it cannot be wrong.

Next — Chapter 06 · The Wall: not every space bends to a clever order of search. This chapter's algorithms all found structure to exploit — the next chapter meets problems with no exploitable structure at all, and asks what a solver does when the space itself refuses to get shorter.