跳轉到

第 4 章　馮·紐曼、波蘭數學家與排序、博弈演算法的創世紀#

4.3 艾茲赫爾·戴克斯特拉與最短路徑演算法：在咖啡館用 20 分鐘想出的地圖導航傳奇#

4.3.1 阿姆斯特丹咖啡館的二十分鐘#

Dijkstra（1930–2002）晚年自述：1956 年，29 歲的他與未婚妻在阿姆斯特丹一家咖啡館，為演示新計算機 ARMAC 的能力而思考「從鹿特丹到格羅寧根的最短路線」，不用紙筆、約 20 分鐘想出演算法。1959 年他把它發表為兩頁半的論文《A note on two problems in connexion with graphs》（Numerische Mathematik）——論文還同時含第一個最小生成樹演算法（ Prim 演算法的荷蘭先行版）。

4.3.2 演算法與複雜度#

維護一個「已確定最短距離」集合，每步貪心選出距離最小的未定點並鬆弛其鄰邊：

\[ d(v) \leftarrow \min\big(d(v),\; d(u)+w(u,v)\big) \]

正確性依賴貪心性質（邊權非負）。複雜度隨數據結構演化：鄰接矩陣 \(O(V^2)\) → 二叉堆 \(O((V+E)\log V)\) → 斐波那契堆 \(O(E + V\log V)\)（Fredman & Tarjan, 1987）。負權邊由 Bellman–Ford（1958）處理——最短路徑家族自此完整。

4.3.3 演算法如何變成日常#

  1. 網路路由：OSPF 協議（RFC 2328）以 Dijkstra 計算最短樹——網際網路的每個路由器都在跑它；
  2. 地圖導航：從車載 GPS 到 Google Maps，A*（Hart–Nilsson–Raphael, 1968，Dijkstra＋啟發式剪枝）成為大規模路網標準；
  3. 學科示範：Dijkstra 本人是「結構化編程」的旗手（1968《GOTO 語句有害論》信件、THE 多道程式系統），1972 年獲圖靈獎——他的程式員品格論（優雅性證明）與最短路徑一樣成為遺產。

4.3.4 前因後果#

  • 前因：荷蘭的數學傳統＋ARMAC 演示需求＋圖論的成熟。
  • 事件：1956 想出、1959 發表。
  • 後果：圖演算法成為計算機科學的核心課程；「貪心＋不變量證明」的方法論（他與 Hoare 的合作傳統）影響整個程式正確性學派；導航、路由、物流的地圖文明由此奠基——第 5 章香農則將奠定「信息」本身的度量。

下一章：第 5 章　香農與霍夫曼