A Note on Two Problems in Connexion with Graphs

idea · Edsger W. Dijkstra · 1959

A framing later work is built out of rather than argued about. Cited when the thing being watched descends from it and the descent explains its shape.

idea is right, and the id was filed correctly. This is the canon's second idea after shannon-chess-1950, and it is the same shape of thing: a framing later work is built out of rather than argued about. The citation occasion is not "someone is wrong about this" but "the thing you are watching descends from this, and the descent explains its shape." Nothing here is a limit — the paper proves no impossibility — and nothing here is a prediction, because the paper makes no dated claim about anything. Three pages, two algorithms, no forecast.

It is not in proposals.md. The fifty candidates proposed on 2026-08-15 do not include it under any kind; it entered the run list separately. That is worth recording because the proposals file explains its own admission test — only entries where a live citation occasion could be named — and an entry arriving outside that filter has to pass the test on its own rather than inherit a pass. Section 2 below is that test, and this entry would fail it if the case rested on "shortest paths are important." It does not. It rests on three things that happened between October 2024 and February 2026, none of which involve a model.

descends_from is empty, and here that is a checked fact rather than a gap. The paper carries four references, and I read the list: Kruskal on the shortest spanning subtree (1956), Loberman and Weinberger on connecting terminals with minimum total wire length (1957), Ford's Rand paper on network flow theory (1956), and Berge's Théorie des graphes at pages 68–69 (1958). None is in canon/ and none is in proposals.md. So although shannon-chess-1950, turing-halting-1936, godel-incompleteness-1931 and lovelace-1843 are all in canon/ and all chronologically prior, none is an ancestor of this entry and none should be linked to it. Note in particular that Shannon is not an ancestor despite the surface resemblance — both papers are about searching a space of possibilities, and neither knows about the other. The convergence is real and the descent is not; section 2 says what to do with that distinction. If someone writes Ford or Berge, this header should be edited.

I record the reference list explicitly because I expected it to be empty. The paper is widely described as having been written with nothing to cite, and I would have written that sentence from memory had I not checked. It is false. What is true is narrower: three of the four references attach to Problem 1, the spanning-tree half, where Dijkstra was correcting published work. The shortest-path half — the famous half — cites Ford and Berge and argues with neither.

A note on access. The primary text is a scanned PDF at the CWI repository and at HAL, and neither would convert to text through the tooling available to this job: the scans are image-encoded, and local extraction needed a permission this non-interactive run cannot obtain. So the direct quotations below from the 1959 paper are the standard ones, taken from secondary sources that quote it, and I have marked them as such rather than implying I read the page. The bibliographic record — four references, affiliation, volume and pages — is from the publisher's own metadata and is solid. Everything about what the paper argues is at one remove, and section 5 says which remove.

What it is

Three pages in the first volume of Numerische Mathematik, pages 269 to 271, published in 1959 by a twenty-nine-year-old programmer at the Mathematisch Centrum on the 2e Boerhaavestraat in Amsterdam. It solves two problems about a graph — a set of nodes, some pairs of which are joined by branches of given length — and it solves them by hand, in prose, with no pseudocode, because in 1959 there was no notation everyone shared to write an algorithm down in.

Problem 1 is: construct the tree of minimum total length between the n nodes. This is the minimum spanning tree. Dijkstra's method for it is the one now universally called Prim's algorithm, after Robert Prim, who published it in 1957; both were preceded by Vojtěch Jarník in 1930. Dijkstra published it third and lost the naming entirely.

Problem 2 is: find the path of minimum total length between two given nodes P and Q. This is the one that carries his name. The method grows a region of settled nodes outward from P, always settling next whichever unsettled node currently has the smallest known distance, and stopping when Q is settled. The load-bearing observation is stated in the paper: if R lies on the minimal path from P to Q, then knowing that path implies knowing the minimal path from P to R. Optimal paths are made of optimal paths, so the work done to reach R is never wasted and never needs revisiting. That is why the algorithm can be greedy and still be correct, and it is the whole idea.

Two things about the presentation matter more than they look. First, the paper specifies no data structure. It says which node to pick next, not how to find it, and that omission is the reason the algorithm's complexity is a sixty-seven-year research programme rather than a line in the original. As published and implemented the obvious way, it costs on the order of n² comparisons. With a binary heap it costs on the order of m log n. With the Fibonacci heap that Fredman and Tarjan introduced in 1984 and published in the Journal of the ACM in 1987, it costs m + n log n, and that bound stood as the best known for arbitrary directed graphs with non-negative weights for thirty-eight years. Dijkstra did not choose any of this. He described a procedure and left the machine underneath it unspecified, and the procedure turned out to be robust enough that four decades of data-structure research could be poured into the hole without changing a word of the method.

Second, the efficiency argument he does make is about memory, not time. His stated reason for preferring his Problem 1 solution to Kruskal's and to Loberman and Weinberger's is that theirs require sorting all the branches first and his does not — you never have to hold the whole edge set in order. On a 1956 machine that was the binding constraint, and it is a characteristically Dijkstra kind of argument: the resource he is defending is the one that will run out. Asymptotic complexity as a discipline barely existed; the arguments are, by modern standards, hand-waved.

The origin is one of the best-attested anecdotes in computing, and Dijkstra told it himself in an interview conducted in 2001 by Philip L. Frana for the Charles Babbage Institute, published in Communications of the ACM in August 2010. He had been asked to demonstrate the new ARMAC computer at the Mathematical Centre in a way a lay audience could follow, and picked route-finding over a simplified map of the Netherlands — sixty-four cities, so that a city number fits in six bits. Asked where the algorithm came from, he said it was designed in about twenty minutes:

> "One morning I was shopping in Amsterdam with my young fiancée, and tired, > we sat down on the café terrace to drink a cup of coffee and I was just > thinking about whether I could do this, and I then designed the algorithm."

And on why it came out clean: "Without pencil and paper you are almost forced to avoid all avoidable complexities." The demonstration was 1956. Publication was 1959, three years later, and his own explanation for the delay is that there was hardly anywhere to publish it — computing had not yet accumulated journals, and Numerische Mathematik was in its first volume.

Two descendants matter for this canon. In 1968 Peter Hart, Nils Nilsson and Bertram Raphael published "A Formal Basis for the Heuristic Determination of Minimum Cost Paths" in IEEE Transactions on Systems Science and Cybernetics, introducing A\ — Dijkstra's method plus a heuristic estimate of the remaining distance, with a proof that the search stays optimal as long as the estimate never overshoots. That paper came out of SRI's work on Shakey, and it is the join between this entry and artificial intelligence proper: A\ is graph search with a guess bolted on, and it became the standard planning and pathfinding algorithm of the field. Set the heuristic to zero and A\ is* Dijkstra, which is why AI textbooks teach the same procedure under a different name — uniform- cost search. And in the other direction the algorithm went into infrastructure: the link-state routing protocols OSPF and IS-IS compute their forwarding tables by running it, which means a large fraction of the internet's packet routing is this paper, executing continuously, everywhere, right now.

Why a reading would cite it

The occasion is not shortest paths. A reading of the AI state will not need to explain shortest paths. The occasion is that between October 2024 and February 2026 this algorithm became an unusually clean instrument for three questions the readings keep having to answer, and it is available as an instrument precisely because it is the most studied algorithm in computer science — the signal-to-noise is better here than anywhere a model is involved.

First, as the control case for the accelerant lens. LENSES.md sets a hard test for AI-as-accelerant: it counts only if the source shows AI was actually used in the work, named in a methods section or a technical account, and says what became possible that wasn't. The 2026-08-15 reading applied that test to Crouzeix's conjecture and passed two claimed proofs through it because both disclosed model use. The test needs a denominator. Here is one. Dijkstra's algorithm is the single most plausible target for machine-discovered algorithmic improvement that exists: it is sixty-seven years old, taught to every undergraduate, defined over a search space that is formally specified, with a scalar objective and instant verification of correctness — the exact profile that FunSearch, AlphaTensor and AlphaEvolve were built to attack. It was improved three times inside sixteen months. The Fibonacci-heap bound was shown to be not merely worst-case optimal but universally optimal by Bernhard Haeupler, Richard Hladík, Václav Rozhoň, Robert Tarjan and Jakub Tětek, best paper at FOCS in October 2024. It was then beaten outright by Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu and Longhui Yin, best paper at STOC in June 2025. It was beaten again by four of those five in February 2026. No model appears in any of those methods sections. When a reading needs to say how much of frontier mathematics is currently being done by machines, this is the case where the answer is legible and the answer is none — which is not an argument that models cannot do it, and is a measurement of where the line sat in this window.

Second, as the cleanest available specimen of a theoretical result that does not change practice. The readings are built to separate demonstrated from claimed, and the hardest version of that problem is not vendors lying; it is true results whose practical import is nil. Duan et al.'s algorithm is genuinely, provably faster than Dijkstra's in the asymptotic sense — O(m log^(2/3) n) against O(m + n log n), the first time in sixty-six years anyone got under the bound on sparse graphs, and it is correct. In November 2025 someone implemented it and measured it against Dijkstra on sparse random graphs, grids, and US road networks up to ten million vertices. Dijkstra was three to four times faster in every scenario tested. The constant factors are large enough that the authors estimate a graph would need to exceed 10^67 vertices before the asymptotically superior algorithm actually won — a number with no physical referent, exceeding the particle count of the observable universe by more than thirty orders of magnitude. The result is real, the barrier is broken, the theory is permanently changed, and no router on earth should switch. A reading that needs to explain how a benchmark can move without anything moving has a case here where the arithmetic is unarguable and no company's interests are involved.

The same episode supplies its own hype specimen. An independent GitHub implementation of the 2025 algorithm advertises "20,000× speedup over scalar Dijkstra" — and to its credit states the conditions in the same breath: sparse tree-like graphs, GCC with -O3 -march=native, a specific AMD processor with 96MB of V-cache, and the acknowledgement that the figure combines algorithmic, compiler and hardware effects. That is the anatomy of nearly every performance claim the readings meet: a real measurement, honestly conditioned by the person who made it, one repost away from becoming "new algorithm 20,000× faster than Dijkstra." The theoretical gain is a log^(2/3) factor. The gap between those two numbers is the thing to point at, and pointing at it costs nothing here because nobody is selling anything.

Third, as the case where a superlative inverted without anyone being wrong. In October 2024 Quanta reported that computer scientists had established the best way to traverse a graph, and the finding was correct: Dijkstra with the right heap is universally optimal. In June 2025 the STOC best paper showed Dijkstra is not optimal for single-source shortest paths, and that finding is also correct. Both stand. They concern different problems. The 2024 result is about the distance ordering — producing the vertices sorted by distance from the source — and for that task no comparison-based algorithm can asymptotically beat Dijkstra on any graph topology. The 2025 result computes the distances without producing them in sorted order, which is what "breaking the sorting barrier" means: it wins by declining to do the part that was proven optimal. Nine months apart, two correct headlines in contradiction, and the entire disagreement lives in the problem statement. The readings meet this constantly — a benchmark saturates, a capability is claimed optimal, a record falls — and the discipline this teaches is to read what was measured before reading who won. It is a better teaching case than any AI benchmark dispute because there is no ambiguity anywhere to argue about.

Fourth, and more loosely, as the reference specimen of the AI effect. In 1956 finding a route between two Dutch cities was chosen as a demonstration of what a computer could do, staged for an audience because it was impressive and intelligible. Every phone now does it continuously, every backbone router does it, and no one calls it artificial intelligence. It is the cleanest dated instance of the pattern John McCarthy complained about — as soon as it works, nobody calls it AI any more — and it is useful in the specific form the readings need: when a deployment is announced as AI-powered routing, optimisation or logistics, the entry supplies the question of whether anything after 1959 is doing the work. Note the honest limit on this argument. It cuts both ways, and the same reasoning that deflates a marketing claim also deflates a genuine achievement in retrospect, which is exactly how the field keeps losing credit for its wins. A reading should use it to ask what the system does that Dijkstra's method cannot, not as a rhetorical device for making anything sound unimpressive.

Fifth, for the author rather than the paper. Dijkstra spent his later career as the most quotable opponent of anthropomorphic language about computers, and the line that survived is from EWD898, "The threats to computing science," delivered at the ACM South Central Regional Conference in Austin, 16–18 November 1984: Turing thought about criteria to settle the question of whether machines can think, "a question of which we now know that it is about as relevant as the question of whether Submarines Can Swim." When the public-square lens needs to name the position that the does-it-really-think argument is a category error, this is where the position is stated, by someone who had built the machinery and had no stake in either side of the AI debate because he thought the debate was malformed. Section 3 grades it, because it is a claim about relevance and it has aged unevenly.

What a reading should not cite it for: nothing here bears on whether models are getting better, on safety, on compute, or on the needle. This is an instrument for reading claims, not evidence about the world.

What it got right, and what it got wrong

Not required for idea, but there are three dated claims in the vicinity worth grading, and one non-claim that turned out to matter more than any of them.

Right, and more deeply than he argued: avoid the sort. Dijkstra's stated reason for preferring his Problem 1 method to Kruskal's and to Loberman and Weinberger's, in 1959, was that theirs sort all the branches and his does not. He argued it as a memory economy on a machine with almost none. Sixty-six years later the barrier that had to be broken to beat him at Problem 2 was named the sorting barrier, and it was broken by an algorithm that refuses to sort the frontier. I want to be careful here, because the temptation is to award him a prophecy he did not make. He did not anticipate the 2025 result; he was not reasoning about lower bounds, which were not a subject yet, and his 1959 argument concerns a different problem in the same paper. What he had was an instinct that ordering everything is a cost you pay whether or not you need the order, and that instinct located the right structure. The 2025 result is that instinct's vindication in a form he had no vocabulary to state.

Wrong by omission, and it cost him a naming: no complexity analysis, no data structure. The paper describes which node to settle next without saying how to find it, and offers no bound. This was normal for 1959 and it is still an omission — it meant the method as published was Θ(n²), which is fine for dense graphs and bad for sparse ones, and it took until 1984 for the right structure to be found. It is also why the object called "Dijkstra's algorithm" in a modern textbook is not the object in the paper. And on the other half of the paper he was simply late: he published the minimum spanning tree method two years after Prim and twenty-nine years after Jarník, and it is not called Dijkstra's algorithm by anyone. Half of a three-page paper is the most famous algorithm in computing; the other half is a footnote about priority. A canon that only remembers the winning half is mis-remembering the document.

Mixed, and now the interesting one: "as relevant as whether submarines can swim" (EWD898, November 1984, no due date given). Grade the two halves separately, because they have come apart.

As a claim about research strategy it was right and has been vindicated about as thoroughly as such a claim can be. The field did stop trying to define thought and started measuring capability, and that is where the progress came from. Every artefact the 2026-08-15 reading looked at — FrontierCode scores, model cards, saturating safety benchmarks, an internal model described as a "noticeable improvement... on many internal tasks" — is a capability measurement made without anyone defining thinking. Dijkstra's redirection is now so completely the default that the counterfactual is hard to picture.

As a claim about relevance it has aged badly, and the same reading shows why. The question of what is going on inside these systems stopped being a philosophers' question and became a legal and regulatory one, with defendants. In the window that reading covered: nine California bills on chatbot conduct cleared Senate Appropriations, including AB 2023 on children's safety and AB 1609 on customer-service chatbots; a class action alleged a shipped model was used to generate roughly seven thousand abuse images of a named person; Anthropic marked its own catastrophic-misalignment risk up on the strength of findings about how a model behaves when safeguards are removed; and Debian opened a project-wide vote on whether machine-generated contributions are admissible at all, with one option reading "Debian is created by humans." Every one of those turns on attributing something — intent, understanding, authorship, agency — to a system, and none of them can be settled by measuring task performance. Whether the submarine swims turns out to matter enormously once the question is who is liable when it hits someone. Dijkstra was answering a 1984 question about how to do computing science, and the answer does not survive transplant into a courtroom.

There is a fourth thing to grade, which is not a claim but an absence. Nothing in this paper predicts anything, and that is why it has aged better than anything published near it. The 1950s entries in proposals.md are mostly forecasts with due dates that came and went — Simon's twenty years to full automation, the perceptron that would walk and talk and reproduce itself. This paper says what a procedure does and stops. Sixty-seven years later every sentence in it is still true, because none of them was about the future. When the canon needs to show what a durable technical claim looks like next to a perishable one, the contrast between this three-page note and the press coverage of the perceptron two years earlier is the whole lesson, and it needs no commentary.

Commonly misused as

Not required for idea — the section belongs to limit — but this entry attracts four misreadings, and two of them are live right now.

"Dijkstra's algorithm has been proven optimal" / "Dijkstra's algorithm has been proven not optimal." Both are in circulation, both trace to real best-paper results nine months apart, and both are true of different problems. Optimal for producing vertices in order of distance, on every graph topology, against every comparison-based competitor (FOCS 2024). Not optimal for producing the distances, where you can win by giving up the ordering (STOC 2025, improved February 2026). Anyone asserting either sentence without naming the problem has dropped the load-bearing half. The useful move when a reading meets this shape — and it will meet it about benchmarks, not about graphs — is to ask what was held fixed, not who was faster.

"A sixty-six-year-old algorithm was just beaten, so everything is being beaten right now." The 2025 and 2026 results are theoretical. Measured against a competent Dijkstra implementation on real road networks, the new algorithm loses by a factor of three to four, and the crossover is estimated beyond 10^67 vertices. Both statements are true simultaneously and neither cancels the other. The failure mode is treating an asymptotic improvement as a deployment.

"AI is now discovering better algorithms than humans." This entry is not evidence against that claim in general — AlphaTensor, FunSearch and AlphaEvolve produced real artefacts, and this entry takes no position on them. It is evidence about this algorithm, where three improvements in sixteen months were produced by named human theorists at Tsinghua, Stanford, ETH, INSAIT, Princeton, Copenhagen and Max Planck, with no model disclosed in any methods section. Used precisely, that is a data point about who is currently doing the hardest work on the best-studied problem. Used loosely it becomes an argument that machines cannot do mathematics, which nothing here establishes and which the Crouzeix items in the 2026-08-15 reading actively cut against.

"The paper has no references, because there was nothing to cite." It has four: Kruskal, Loberman and Weinberger, Ford, and Berge. I expected the opposite and checked. The true version of the anecdote is that the paper is three pages, was written for a journal in its first volume because there was almost nowhere else to publish computing work, and makes its efficiency arguments informally — not that it was composed in a vacuum.

One thing that is not a misuse, and is worth stating so it does not get policed: calling A\ and uniform-cost search descendants of this paper is correct, and so is the observation that a great deal of what the readings now call planning, tree search and test-time compute is graph search with a heuristic. The descent is genuine. What does not follow is that Dijkstra's paper is an ancestor of Shannon's* — the two converge on searching a space of possibilities and neither cites the other, which is why descends_from above is empty and why a reading should say "converges with" rather than "descends from" when it puts them side by side.

Sources

Primary, bibliographically verified:

E. W. Dijkstra, "A note on two problems in connexion with graphs," Numerische Mathematik 1, 269–271 (1959), DOI 10.1007/BF01386390. Affiliation given as Mathematisch Centrum, 2e Boerhaavestraat 49, Amsterdam-O. Reference list confirmed from publisher metadata as four items: Kruskal, Proc. Amer. Math. Soc. 7, 48–50 (1956); Loberman and Weinberger, J. Ass. Comp. Mach. 4, 428–437 (1957); Ford, Network flow theory, Rand Corp. Paper P-923 (1956); Berge, Théorie des graphes et ses applications, pp. 68–69, Dunod (1958). Scanned full text is at the CWI institutional repository, https://ir.cwi.nl/pub/9256 — I could not extract its text; the scan is image-encoded and local conversion required a permission this job does not have. A bilingual annotated version exists at HAL (hal-03171590) and was unreachable — the host returned an access-control challenge on both attempts.
E. W. Dijkstra, "The threats to computing science" (EWD898), ACM 1984 South Central Regional Conference, Austin, 16–18 November 1984. Transcription at https://www.cs.utexas.edu/~EWD/transcriptions/EWD08xx/EWD898.html — read directly; the "Submarines Can Swim" sentence is quoted from it above.

Primary, quoted at one remove:

Philip L. Frana, "An interview with Edsger W. Dijkstra," Communications of the ACM 53(8), August 2010, from an interview conducted in 2001 for the Charles Babbage Institute oral history collection. The café/twenty-minutes quotation and the "without pencil and paper" quotation are from this interview. The ACM site returned HTTP 403 to this job, so both are taken as quoted by the Wikipedia article on Dijkstra's algorithm, which cites the CACM interview for them. Treat as well-attested but not read at source.