Edsger Dijkstra and the Shortest-Path Algorithm: Greedy Choice on a Graph
Edsger Dijkstra's shortest-path algorithm repeatedly finalizes the nearest reachable vertex, turning weighted-route search into a disciplined greedy process with a provable invariant.
Dijkstra designed the algorithm for a public computer demonstration
Edsger W. Dijkstra later recalled that he designed his shortest-path algorithm for the 1956 inauguration of the ARMAC computer at Amsterdam’s Mathematical Centre. He wanted a problem understandable to a general audience: finding the shortest route between cities.[2]
That origin is revealing. The algorithm became a foundation of graph theory in computing, yet it began as a concise demonstration of what a programmable computer could do.
The first version was designed before it was formally published
Dijkstra wrote that the idea came together without pencil and paper and was not published until 1959 because discrete algorithms did not yet have an obvious scholarly home. That gap shows how young algorithmics was as a recognized field.
The 1959 paper addressed two graph problems in only a few pages
Dijkstra’s paper “A note on two problems in connexion with graphs” presented methods for a minimum spanning tree and for shortest paths.[1] The shortest-path procedure grows a set of vertices whose best distances are already known.
At every step, the method chooses the not-yet-finalized vertex with the smallest tentative distance and uses its outgoing edges to improve neighboring estimates.
A tentative distance is a promise, not yet a fact
The algorithm can discover several candidate routes to the same vertex. A distance becomes final only when that vertex is selected as the smallest remaining tentative value under the nonnegative-weight assumption.
The greedy step works because edge lengths are nonnegative
Once the algorithm chooses the smallest tentative distance, no later route through an unvisited vertex can make it smaller if all remaining edge weights are nonnegative. This invariant is the source of correctness, not merely the mechanics of a priority queue.
Modern teaching materials continue to emphasize that the method solves single-source shortest paths in weighted graphs under this condition.[4]
Negative edges break the finalization argument
A negative edge can create a cheaper route after a vertex has been declared finished. That is why other shortest-path algorithms are needed when negative weights are permitted.
The data structure changed the running time without changing the algorithmic idea
The original implementation reflected the machines of its era. Later implementations use priority queues so the smallest tentative distance can be selected efficiently. The conceptual algorithm—relax edges, choose the nearest unfinished vertex, repeat—remains the same.
This separation between algorithm and data structure became a recurring theme in computer science: the abstract method can survive while better representations improve its cost.
Priority queues made sparse graphs especially attractive
With heap-based implementations, the amount of work can track vertices and edges more closely than a simple repeated scan. This is one reason the same algorithm remains practical on large sparse networks.
The shortest-path problem became a model for reasoning with invariants
Dijkstra was famous for insisting that programming be justified by clear mathematical reasoning. His shortest-path algorithm is a compact example: maintain a frontier, preserve an invariant about finalized distances, and show that each greedy choice keeps the invariant true.
CWI’s historical profile describes the algorithm as a cornerstone of his fame and traces it from the ARMAC demonstration to widespread later use.[3]
Routing and navigation made the algorithm culturally visible
The shortest-path problem appears in road planning, communication networks, logistics and dependency graphs. Dijkstra himself later remarked on the algorithm’s use in travel planners, while modern university treatments still introduce it through route finding.[2][4]
Real systems often add heuristics, hierarchy or specialized graph structures, but Dijkstra’s formulation remains the baseline against which many improvements are explained.
The published record also preserves the historical context
Eindhoven University of Technology’s research portal records the original 1959 Numerische Mathematik publication, while Dijkstra’s autobiographical notes explain that the algorithm had been conceived three years earlier.[5][2]
Separating invention date from publication date matters in computing history because algorithms often circulate in demonstrations, code and internal work before they appear in journals.
Why Dijkstra’s shortest-path algorithm belongs in coding history
The algorithm gave programmers a reusable method for turning local edge costs into globally shortest routes through a graph. More importantly, it demonstrated how a greedy choice can be made safe by a precise invariant.[1]
Its longevity comes from that combination of simplicity and proof: choose what is currently cheapest only when the problem structure guarantees that the choice can never need to be undone.
Works Cited
- 01
- 02E.W. Dijkstra Archive — From my Life (EWD 1166) cs.utexas.edu
- 03
- 04Cornell University — The shortest-path algorithm cs.cornell.edu
- 05
CodeHistory is a living archive. Citations document the evidence used for this edition; later evidence may refine the account.
Submit a research lead