算法 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