案例库 · 软件与 IT · 技术决策 · 1959–1970
迪杰斯特拉的一次有序扫描让最短路径路由成为已解决问题
一篇1959年的三页笔记展示了如何通过总是扩展最近未确定节点来从一个点找到到所有其他点的最短路径。
阿姆斯特丹数学中心
那一手
在1950年代，在城市、电话交换机或道路交叉口之间寻找最短路径是一项手工且组合繁琐的工作。艾兹格·迪杰斯特拉在1959年写了一篇三页的笔记，表明问题——从一个源点到具有非负权重的图中所有节点的最短路径——有一个简单的精确解。
其思想是向外扩展一个已确定区域：每一步，取具有最小当前距离的未确定节点并将其标记为最终值，因为任何到它的替代路径都必须经过一个至少已经确定距离的节点。然后更新它的邻居。这样的一次扫描只需要一个优先队列，因此运行时间接近线性。
这个看似贪心的方法实际上对非负权重是可证明最优的，同一有序扩展思想成为了导航系统、道路网络、互联网路由和物流中路径规划的主干。
为什么管用
- 按距离顺序确定节点保证了每个最终距离是最优的，消除了回溯。
- 该算法每个节点只需要一次通过加上一个优先队列，因此可以扩展到真实的道路和网络图。
- 实现和验证简单，这是它几十年来被内置在导航和路由产品中的原因。
- 它解决了一类问题（单源最短路径）而不是单个实例。
值了多少先确定最近节点；每个距离都是最终值神来之笔
可以搬走什么
一个好的算法通常用一次有序的扫描取代反复的全局搜索——先处理确定的简单情况，剩余的自然就解决了。
后来呢
迪杰斯特拉算法成为计算机科学中教授最多和使用最多的算法之一，是GPS导航、网络路由和物流软件的标准组件。后来的改进（A*、双向搜索、高速路分层）直接建立在其有序扩展原则之上。
资料来源
发现哪里写错了？告诉我们。