Bellman-Ford vs Dijkstra:在什么情况下Bellman-Ford更好？

Question

经过大量的谷歌搜索后,我发现大多数消息来源称Dijkstra算法比Bellman-Ford算法"更有效".但在什么情况下Bellman-Ford算法比Dijkstra算法更好？

我知道"更好"是一个广泛的陈述,所以具体来说,我的意思是速度和空间,如果适用.当然,在某些情况下,贝尔曼 - 福特方法比Dijkstra方法更好.

Answer 1

Bellman-Ford algorithm is a single-source shortest path algorithm, so when you have negative edge weight then it can detect negative cycles in a graph.

The only difference between two is that Bellman Ford is capable also to handle negative weights whereas Dijkstra Algorithm can only handle positives.

From wiki

However, Dijkstra's algorithm greedily selects the minimum-weight node that has not yet been processed, and performs this relaxation process on all of its outgoing edges; in contrast, the Bellman–Ford algorithm simply relaxes all the edges, and does this |V | − 1 times, where |V | is the number of vertices in the graph. In each of these repetitions, the number of vertices with correctly calculated distances grows, from which it follows that eventually all vertices will have their correct distances. This method allows the Bellman–Ford algorithm to be applied to a wider class of inputs than Dijkstra.

然而,由于典型的二进制堆优先级队列实现具有O((| E | + | V |)log | V |)时间复杂度[D斐波纳契堆优先级队列给出O(D) | V | log | V | + | E |)],而Bellman-Ford算法具有O(| V || E |)复杂度

Answer 2

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

Answer 3

我知道它们之间有 4 个主要区别：

1. 如果使用最大堆，贝尔曼时间复杂度为 O(VE)，Dijkstra 算法为 O(Elog(V))。
2. Bellman 松弛了 V-1 次，而 Dijkstra 算法只松弛了 1 次。
3. Bellman 可以处理负权重，但 Dijkstra 算法不能。
4. Bellman 多次访问一个顶点，但 Dijkstra 算法只访问一次。