Bellman-Ford 算法
- 提出者
- Richard Bellman and Lester R. Ford
- 年份
- 1956
- 类型
- algorithm
- 类别
- Graph Algorithms
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
Bellman-Ford 算法由 Richard Bellman 和 Lester R. Ford 于 20 世纪 50 年代开发,是一种用于计算带负数边权图的最短路径的基本算法。与 Dijkstra 算法不同,它能正确处理负权边,并能检测负权环的存在。
方法背后的直觉
该算法通过迭代地松弛边来工作:对于每条边,它会检查通过该边到达目标顶点的路径是否比当前已知的最佳路径更短。通过对所有边重复此过程 V-1 次(其中 V 是顶点数),该算法保证即使存在负权边也能找到最短路径。关键在于,任何具有 V 个顶点的图中的最短路径最多包含 V-1 条边;如果在 V-1 次迭代后距离仍有改善,则必然存在负权环。
历史学
该算法由 Richard Bellman 于 1958 年利用动态规划原理开发,而 Lester R. Ford 于 1956 年独立发现了网络流的类似方法。该算法在 20 世纪 60 年代得到了进一步的开发和改进,并扩展到网络路由和经济应用。现代变体包括“最短路径更快算法”(SPFA) 和针对特定图结构的各种优化,但基本的 Bellman-Ford 方法仍然是算法设计中的经典参考。
何时使用
在计算带负权边的图的最短路径时应用 Bellman-Ford 算法。它对于货币套利检测、权值可能为负的网络协议以及任何涉及负成本或负权值的应用至关重要。如果所有权值均为非负,则应使用 Dijkstra 算法,因为它更有效。该算法也适用于在不计算路径的情况下检测负权环。
局限与注意事项
- 对于非负权边,比 Dijkstra 慢:O(VE) 对比 O((V+E)logV)
- 对于稀疏图,效率低于其他算法
- 需要列出所有边,因此不太适合隐式或动态图
- 没有可用的启发式引导来加速计算
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 正确处理带负权边的图
- 检测负权环,防止最短路径结果错误
- 比某些高级最短路径算法更易于理解和实现
- 保证在 O(VE) 时间内找到最短路径
- 可用于有向图和无向图(无向图需谨慎)
应用
- 货币套利检测:识别汇率图中的盈利环
- 网络路由协议:计算链路成本可能变化或为负的最短路径
- 博弈论:用惩罚边或折扣因子解决最短路径问题
- 机器人学:在具有排斥力(负权)的环境中进行路径规划
- 经济调度:优化包含负项的成本函数的发电
- 电信:在链路权重代表延迟或质量指标时寻找最优路由
使用方式
使用方式
将源顶点的距离设置为零,所有其他顶点的距离设置为无穷大;可选地,将所有前驱节点设置为 null。
重复 V-1 次:对于每条边 (u, v) 及其权重 w,如果 distance[u] + w 小于 distance[v],则更新 distance[v] 和 v 的前驱节点。
再检查所有边一次;如果任何距离有所改善,则存在负权环。根据需要返回错误或识别出环。
常见陷阱
- 忘记执行额外的迭代来检测负权环
- 假设算法在带负权的无向图上能正确工作(可能产生虚拟负权环)
- 在 Dijkstra 已足够的情况下使用该算法,导致不必要的性能损失
常见问题
为什么该算法需要精确 V-1 次迭代?
具有 V 个顶点的图中的任何路径最多包含 V-1 条边。通过迭代 V-1 次,该算法允许距离信息传播到整个图。只有当存在负权环时,第 V 次迭代才会改善距离。
该算法如何检测负权环?
完成 V-1 次迭代后,再进行一次松弛。如果任何距离有所下降,则存在负权环。可以通过使用前驱节点指针进行回溯来识别环中的节点。
时间复杂度是多少?与 Dijkstra 相比如何?
Bellman-Ford 的运行时间为 O(VE),其中 V 是顶点数,E 是边数。Dijkstra 使用二叉堆的运行时间为 O((V+E)logV)。Bellman-Ford 较慢但能处理负权边;Dijkstra 较快但需要非负权边。
Bellman-Ford 能在带负权边的无向图上工作吗?
技术上可以,但由于边的双向性,可能会产生虚假的负权环。需要特别注意正确解释结果。对于无向图,应考虑其他方法。