演算法 1959

關於圖的兩個問題的一則短論

艾茲格·W·戴克斯特拉

永遠先把目前最便宜的那條路線往外延伸，通往各處的最短路徑便自然浮現。

Choose your version

In depth · the introduction

你的手機怎麼能在一眨眼之間，從一整個國家那麼多條路裡，挑出唯一最快的那條——還不必把它們一一檢查過來？

核心想法

假設你想在一張公路地圖上，求出從你所在的城鎮到其餘每一座城鎮的最短路線。蠻力的辦法——把每一條可能的路線都試一遍——會膨脹成多得不可能算完的組合。戴克斯特拉找到了一條捷徑，它建立在一個守紀律的習慣之上：永遠先把你目前找到的最便宜的那條路線往外延伸。

從家出發，距離記為零，把其餘每座城鎮都標為「距離未知」。然後反覆做同一件小事：在還沒鎖定的城鎮裡，挑出此刻你能最便宜抵達的那一座，把這個距離作為最終值鎖定，再用它去更新它的鄰居。因為道路的長度從不為負，你能抵達的最便宜的那座城鎮，日後不會經由別的路反而變得更便宜——所以一旦鎖定，就與它兩清了。如此繼續，通往各處的最短路徑便自然浮現，而每一條都恰好被確定一次。

它是如何誕生的

1956 年，阿姆斯特丹數學中心的年輕程式設計師艾茲格·戴克斯特拉，需要為一台新電腦 ARMAC 做一個生動的示範。他挑了一個人人都能領會的問題：從鹿特丹開車到格羅寧根，最短的走法是什麼？他和未婚妻逛街逛累了，坐在一家咖啡館的露台上，手邊沒有紙筆，便在腦子裡用大約二十分鐘把整套方法想了出來。

他直到 1959 年才把它發表，那是一篇三頁的短論，悄悄地一次解決了兩個圖問題——最短路徑，以及把每個節點都連起來的「最短長度的樹」。戴克斯特拉對署名很謹慎：那個生成樹演算法，多年前已由雅爾尼克和普里姆找到，最短路徑的想法也有別人觸及過。讓他這一版得以流傳的，是它有多乾淨，以及他能說清它為何總是奏效。

它為何重要

這段小小的程式，後來成了有史以來用得最多的演算法之一。每當導航應用為你畫出路線、快遞公司為車隊排班、或一小包資料在網際網路上一跳一跳地穿行，戴克斯特拉方法的某個後裔，正在為穿越一張網路挑選最便宜的走法。它快到能在極大的地圖上運行，又簡單到可被證明正確——這是一種難得而寶貴的組合。

一個可以想像的畫面

想像你往家鄉所在的那張管道網裡灌水，每根管子的長度就是一條路的行車時間。水向外鋪開，總是先經由最短的那根管子抵達每個接頭——絕不會繞遠路先到，因為近路總是先到。水一碰到某個接頭，你就知道通往它的最快時間已成定數。戴克斯特拉演算法正是這場漫流，只不過一次只灌一個接頭：永遠先灌最近的那個乾著的接頭。

它的位置

1950 年代給了計算它的語法：香農量化了資訊，馮·諾伊曼勾勒出儲存程式的機器，而如今戴克斯特拉展示了如何讓這樣的機器高效地對網路作出推理。他的方法，是 A*（同一個想法，被朝著目標輕輕一推）以及把網際網路織在一起的那些路由協定的祖先。在本館裡，它與香農、馮·諾伊曼並立，同為電腦科學的奠基思想之一——也與它同領域的那些密碼學論文比鄰而居，因為它所路由的那張網路，正是它們所要保密的同一張。

The original document

Original source text

E. W. Dijkstra · Numerische Mathematik 1 (1959): 269–271 · Mathematisch Centrum, Amsterdam

The setting

The note opens on a graph of n nodes in which some, or all, pairs of nodes are joined by a branch carrying a given positive length, and asks two construction problems about it. (Paraphrased; the exact statements of the two problems are quoted below.)

Problem 1 — the minimum spanning tree

Construct the tree of minimum total length between the n nodes.

Dijkstra's solution grows a single tree: start from an arbitrary node and repeatedly add the shortest branch that joins a node already in the tree to a node not yet in it, until all n nodes are connected. (This rule had in fact been found earlier — by Jarník in 1930 and Prim in 1957 — and is usually called Prim's algorithm today.)

Problem 2 — the shortest path

Find the path of minimum total length between two given nodes

Here he keeps the nodes in three groups: those whose minimal distance from the start is already known and fixed; the frontier nodes for which a tentative distance has been found; and the rest, not yet reached. At each step the frontier node of smallest tentative distance is moved into the known set, and the branches leaving it are examined to see whether they offer any of its neighbours a shorter route than the one recorded so far — the step the modern literature calls “relaxing” an edge. (Paraphrased.)

[ … ]

The whole argument fits on three printed pages, with no formal pseudocode in the modern sense; the construction is given in prose. The complete note, including Dijkstra's remarks on storage and on the number of comparisons each method needs, is available at the source below.

Mathematisch Centrum, Amsterdam · 1959