Lesson 8 of 81956–19598 min
Graphs: BFS, DFS and Dijkstra
One morning in 1956 Edsger Dijkstra was shopping in Amsterdam with his fiancée. Tired, they sat down on a café terrace, and he worked out how to find the shortest route between two Dutch cities. He later called it "a twenty-minute invention". He wanted a problem that non-mathematicians could understand, to show off a new computer, the ARMAC.
He did not publish it until 1959, as a three-page note in Numerische Mathematik. Today the same algorithm, in the form of the link-state routing protocol OSPF, decides how packets cross large corporate networks.
The rest of this lesson is part of Pro
Create a free account to read the first lesson of every path, and go Pro for the rest.
Sources
- A note on two problems in connexion with graphs (E. W. Dijkstra, 1959) — Numerische Mathematik
- CS2110: the history of Dijkstra's shortest-path algorithm — Cornell University
- Algorithms, 4th edition, §4.1 Undirected Graphs — R. Sedgewick and K. Wayne, Princeton University
- Algorithms, 4th edition, §4.4 Shortest Paths — R. Sedgewick and K. Wayne, Princeton University