60

经过大量谷歌搜索，我发现大多数消息来源都说 Dijkstra 算法比 Bellman-Ford 算法“更有效”。但是在什么情况下，Bellman-Ford 算法优于 Dijkstra 算法呢？

我知道“更好”是一个宽泛的说法，所以我特别指的是速度和空间（如果适用的话）。在某些情况下，Bellman-Ford 方法肯定比 Dijkstra 方法更好。

4

6 回答 6

68

Bellman-Ford 算法是一种单源最短路径算法，因此当您具有负边权重时，它可以检测图中的负循环。

两者之间的唯一区别是 Bellman-Ford 也能够处理负权重，而 Dijkstra 算法只能处理正权重。

来自维基

然而，Dijkstra 算法贪婪地选择尚未处理的最小权重节点，并对其所有出边执行此松弛过程；相比之下，Bellman-Ford 算法只是简单地放松所有边缘，并且这样做 |V | − 1 次，其中 |V | 是图中的顶点数。在每次重复中，具有正确计算距离的顶点数量都会增加，由此得出最终所有顶点都将具有正确的距离。这种方法允许 Bellman-Ford 算法应用于比 Dijkstra 更广泛的输入类别。

然而，Dijkstra 在没有负权边的情况下通常被认为更好，因为典型的二进制堆优先级队列实现具有 O((|E|+|V|)log|V|) 时间复杂度 [斐波那契堆优先级队列给出 O( |V|log|V| + |E|)]，而 Bellman-Ford 算法的复杂度为 O(|V||E|)

于 2013-10-20T20:15:58.550 回答
11

如所选答案中所述，Bellman-Ford 对所有顶点进行检查，Dijkstra 仅对迄今为止计算出的最佳距离的一个顶点进行检查。同样已经注意到，这提高了 Dijkstra 方法的复杂性，但是它需要比较所有顶点以找出最小距离值。由于这在 Bellman-Ford 中不是必需的，因此在分布式环境中更容易实现。这就是它用于距离矢量路由协议（例如 RIP 和 IGRP）的原因，其中主要使用本地信息。相反，要在路由协议中使用 Dijkstra，首先必须分布整个拓扑，这就是链路状态协议中发生的情况，例如 OSPF 和 ISIS。

于 2017-10-24T11:59:26.627 回答
4

唯一的区别是 Dijkstra 的算法不能处理 Bellman-ford 处理的负边权重。而且 bellman-ford 还告诉我们图是否包含负循环。如果图不包含负边，那么 Dijkstra 总是更好。

Bellman-ford 的一个有效替代方案是使用拓扑排序的有向无环图 (DAG)。

http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/

于 2016-09-22T15:49:54.493 回答
4

我知道它们之间有 4 个主要区别：- 1. bellman 时间复杂度为 O(VE)，而 Dijkstra 算法在使用 maxheap 的情况下具有 O(ElogV)。

  1. Bellman 放松了 n-1 次，而 Dijkstra Algo 只放松了 1 次。
  2. Bellman 可以处理负权重，但 Dijkstra Algo 不能。
  3. 贝尔曼不止一次访问一个顶点，但 Dijkstra 算法只访问一次。
于 2019-05-08T08:33:40.277 回答
2

Dijkstra
算法 Dijkstra 算法无法区分图中是否存在负边权重循环

1. 正边权重：-如果图中的所有边权重均为正， Dijkstra总是 通过
2. 负边权重。和没有 -ve 边缘重量。循环：- Dijkstra总是 通过，即使我们有一些边权重为负，但图中没有循环/循环具有负边权重。
[即不存在负边权重循环]
3. 负边权重。和 -ve 边缘重量。循环：- Dijkstra可能会 通过/失败，即使我们有一些边权重为负，而图中的循环/循环具有负边权重。

于 2017-08-19T13:06:35.073 回答
-7

我不完全同意，区别在于实现和复杂度，Dijsktra 的算法更快（O（n^2））但难以实现，而 Bellman Ford 复杂度为 O（n^3）但更容易实现。

于 2015-06-29T14:19:05.537 回答