Edsger Dijkstra

Life and career

The shortest path algorithm was designed in about twenty minutes, in 1956, in a café in Amsterdam, without pencil or paper, while its author and his fiancée were drinking coffee. Dijkstra told the story many times and always drew the same moral: the absence of paper forced him to avoid all avoidable complexity, and that is why the algorithm is simple enough to have survived. He was demonstrating the power of the ARMAC computer to a lay audience and needed a problem whose statement anyone could understand — the shortest route between two Dutch cities. He did not publish it for three years, and then only in a three-page note, because in the 1950s writing algorithms was not considered a respectable scientific activity.

Edsger Wybe Dijkstra was born in Rotterdam in 1930, to a chemist father who was president of the Dutch Chemical Society and a mathematician mother. He read theoretical physics at Leiden but was drawn into computing at the Mathematical Centre in Amsterdam, where he became, by his own account, the Netherlands' first professional programmer — an occupation that did not officially exist, which caused an actual bureaucratic problem when he tried to register his marriage in 1957 and the authorities refused to accept "programmer" as a profession. He wrote "theoretical physicist."

He wrote the first ALGOL 60 compiler with Jaap Zonneveld, a landmark implementation that handled recursion and introduced the runtime stack for procedure activation records. In 1962 he took a chair at the Eindhoven University of Technology, where he led the THE multiprogramming system — an operating system built as a strict hierarchy of layers, each providing an abstraction the layer above could reason about without knowing the implementation below. In 1973 he became a Burroughs Corporation Research Fellow, an unusual arrangement in which his office was his study at home in Nuenen, he traveled and consulted, and he wrote. In 1984 he moved to the University of Texas at Austin, where he held a chair until retiring in 1999.

The EWD series is inseparable from the man. From the 1960s onward Dijkstra wrote numbered manuscripts — over 1,300 of them — in an immaculate fountain-pen hand, on mathematics, program construction, and the state of computing, and circulated them by photocopy to a self-organizing distribution list. They are acerbic, aphoristic, and frequently very funny at someone's expense. "Go To Statement Considered Harmful" (1968) began as one. He held strong and publicly stated views: that computer science is a branch of mathematics, that programming should be taught before students touch a machine, that "computer science is no more about computers than astronomy is about telescopes," and that most of the industry's problems came from a refusal to think before typing.

He received the Turing Award in 1972, at forty-two, one of the youngest recipients. He returned to the Netherlands in 2002 and died in Nuenen that August, of cancer.

Key contributions

**Dijkstra's algorithm (1959).** Single-source shortest paths in a graph with nonnegative edge weights. Maintain a tentative distance to every vertex, repeatedly extract the unvisited vertex with the smallest tentative distance, finalize it, and relax its outgoing edges. The correctness argument is a clean greedy exchange: because weights are nonnegative, the closest unfinalized vertex cannot be improved by any path through a farther one. With a Fibonacci heap the complexity is *O*(*E* + *V* log *V*). Its structural importance to this audience is that it is the parent of A\*: add an admissible heuristic to the priority key and you get informed search, which is how modern route planning, planning in AI, and much of combinatorial optimization actually run.

**Concurrency primitives.** Dijkstra formulated the **mutual exclusion problem** and gave the first software solution, then introduced **semaphores** (the P and V operations, from Dutch *proberen* and *verhogen*) as the primitive for coordinating concurrent processes. He posed and solved the **dining philosophers problem** as a teaching abstraction for deadlock and resource contention, articulated the **banker's algorithm** for deadlock avoidance, and later developed **self-stabilization** (1974) — the idea that a distributed system should converge to a legitimate state from any arbitrary starting configuration, without central coordination. Self-stabilization was largely ignored for a decade and is now a foundational concept in distributed and fault-tolerant systems; Leslie Lamport's advocacy is credited with reviving it.

**Structured programming.** The 1968 letter arguing against unrestricted `goto` was not a style complaint. Dijkstra's argument was about the relationship between the static text of a program and its dynamic execution: with only sequencing, selection, and iteration, you can characterize where a computation is with a small amount of state, so you can attach an invariant to each point and reason about it. Arbitrary jumps destroy that correspondence and with it the possibility of proof. The book *Structured Programming* (1972, with Hoare and Ole-Johan Dahl) made the case fully, and Dahl's contribution on data abstraction pushed toward object-oriented design.

**Program derivation and weakest preconditions.** *A Discipline of Programming* (1976) is Dijkstra's deepest technical contribution. He defines a predicate transformer wp(*S*, *R*) — the **weakest precondition** — as the set of states from which executing statement *S* is guaranteed to terminate in a state satisfying *R*. Give wp rules for assignment, sequencing, alternation, and repetition, and program semantics becomes a calculus. The consequence he cared about is directional: rather than write a program and then try to verify it, you start from the specification and *derive* the program, letting the required postcondition and loop invariant dictate the code. He also introduced the guarded command language, with nondeterministic selection and repetition, as the vehicle for this — a small language designed so that reasoning about it would be tractable.

His related aphorism — that program testing can be used to show the presence of bugs, but never to show their absence — is one of the few genuinely famous sentences in computer science, and it is the thesis of his career in one line.

In battle

Dijkstra's numbers are unusually solid: mean 32.7, median 31 (nearly equal, which signals a genuinely broad rather than spiky profile), seven dominant scores, and only thirty-eight problems below 20. He is a strong general card within computing and a dead weight outside it.

His peak is **Prove the program correct** (P048) at 96, which is his slogan and his method both. The weakest-precondition calculus lets you compute exactly the condition under which a routine cannot overflow or divide by zero, and the structured-programming campaign existed to make programs amenable to that reasoning in the first place. Characteristically, he would object to the problem's framing — one does not verify a finished program, one constructs a correct one — but on establishing that bad states are unreachable for every input, no one applies more directly.

**Shortest path through the map** (P046) at 95 is the café algorithm. **A hundred robots, no collisions** (P197) at 92 is distributed coordination and mutual exclusion, where semaphores, deadlock avoidance, and self-stabilization are all directly on point. **The machine that overdosed** (P248) at 89 is the Therac-25 radiation therapy failures — a case caused by race conditions in concurrent code and by reliance on testing rather than proof, which is the exact failure mode he spent thirty years warning about. **A computer shared by fifty** (P245) at 85 is time-sharing, where the THE system's layered design is a canonical answer. **The wall around the data structure** (P254) at 82 is abstraction and information hiding, adjacent to his layering discipline though the specific formulation belongs to Parnas and Liskov. **Schedule the moonshot** (P049) at 80 is critical-path scheduling on a DAG, a graph algorithm in his idiom. Even **Decode the hidden path** (P038) at 65 rewards him, because Viterbi decoding is dynamic programming over a graph and Dijkstra's algorithm is its close relative.

His category means are exactly what you would expect: `systems` 65.5, `search` 55.8 across fourteen problems, `computability` 37.7 across sixteen, `networks` 34.2.

The losses are total, not partial. He scores 5 on **Count the fish you cannot see** (P103, capture-recapture estimation), 5 on **Squeeze the estimator dry** (P106, efficiency and Cramér–Rao), 4 on **The spam in the inbox** (P144, naive Bayes classification), 3 on **Counting accidents** (P136, Poisson regression), 3 on **The same patients, measured again and again** (P137), and 3 on **The pixel you cannot see** (P152, adversarial examples). His `classification` mean is 3.5 and his `regression` mean 3.0 — among the lowest figures anywhere in the game.

The adversarial examples score deserves a note because it is thematically tempting and technically empty. Dijkstra's insistence on provable correctness stands in obvious philosophical tension with deep learning's empirical brittleness, and a student might expect him to score well there. He does not, and the game is right: philosophical resonance is not a method. He died in 2002, more than a decade before the discovery, and nothing in predicate transformers gives you a gradient-based attack or a robustness certificate.

He is also, more subtly, weak on *optimization* (25.0 across thirteen problems) despite being an algorithms person, because most optimization problems in the roster are continuous and numerical rather than combinatorial and discrete. Dijkstra's mathematics is discrete, exact, and adversarial-to-all-inputs. Where the question is "what will happen on average, given noise," he has no vocabulary at all. Play him on graphs, concurrency, correctness, and systems design; keep him far away from anything with an error term.