最短路径算法

最短路径算法计算加权图中顶点之间的最小权重路径，不同的算法适用于非负权重、负权重以及所有对与单源查询。

Definition

加权图中两个顶点之间的最短路径是指总边权重最小的路径；最短路径算法计算此类路径及其距离，无论是从一个源到所有顶点，还是在所有顶点对之间。

Scope

本主题涵盖单源最短路径（Dijkstra 算法用于非负权重，Bellman-Ford 算法用于包含负权重的图和检测负环）、所有对最短路径（Floyd-Warshall 算法，Johnson 算法）以及有向无环图中的最短路径。它讨论了这些方法共有的松弛原理以及优先队列在高效实现中的作用。它不包括通过广度优先搜索获得的无权重最短路径，这部分内容在图遍历中讨论。

Core questions

• 边松弛如何逐步收紧距离估计以接近真实的最短距离？
• 为什么 Dijkstra 算法要求非负边权重才能正确？
• Bellman-Ford 如何处理负权重并检测负环？
• 何时计算所有对最短路径比重复单源方法更有效？
• 优先队列的选择如何影响 Dijkstra 算法的运行时间？

Key concepts

• 边松弛
• 单源最短路径
• Dijkstra 算法
• Bellman-Ford 算法
• 负权重环
• 所有对最短路径
• Floyd-Warshall 算法
• 优先队列实现

Key theories

边松弛和贪婪选择

最短路径算法重复松弛边，当发现更短的路径时替换距离估计；Dijkstra 算法贪婪地确定最近的未确定顶点，这正是因为边权重是非负的，所以它是正确的。

所有对路径的动态规划

Floyd-Warshall 算法通过对中间顶点进行动态规划来计算所有对最短路径，运行时间为立方级，并且自然地处理负边权重（没有负环）。

Clinical relevance

最短路径算法为导航和地图服务、网络中的数据包路由协议、物流中的路线规划以及任何在加权网络中寻找成本最低路径的系统提供支持，包括游戏寻路和空间分析中的资源距离计算。

History

Dijkstra 于 1959 年发表了他的单源最短路径算法。Bellman-Ford 算法处理负权重，它是在 1950 年代后期由 Bellman、Ford 和 Moore 的工作发展而来的。Floyd 于 1962 年提出的算法，基于 Warshall 的传递闭包方法，提供了一种紧凑的所有对解决方案，至今仍是标准。

Key figures

• Edsger W. Dijkstra
• Richard Bellman
• Lester Ford
• Robert W. Floyd

Seminal works

• dijkstra1959
• floyd1962
• cormen2009

Frequently asked questions

为什么 Dijkstra 算法不能处理负边权重？

Dijkstra 算法确定最近的未确定顶点并从不重新访问它，假设之后不会有更短的路径。负边可能会在顶点确定后创建这样一条更短的路径，从而打破这一假设。因此，通常使用 Bellman-Ford 算法，它会重复松弛所有边。

何时应该使用所有对算法而不是从每个顶点运行 Dijkstra 算法？

对于稠密图或当需要许多或所有源-目标距离时，Floyd-Warshall 算法的简单立方时间所有对计算通常更受欢迎。对于稀疏图，从每个源运行 Dijkstra（或对于负权重使用 Johnson 算法）在渐近上可能更快。