贝尔曼·福特vs迪克斯特拉：在什么情况下贝尔曼·福特更好？ [英] Bellman-Ford vs Dijkstra: Under what circumstances is Bellman-Ford better?

问题描述

经过大量的Google搜索，我发现大多数消息人士说Dijkstra算法比Bellman-Ford算法更有效。但是在什么情况下Bellman-Ford算法比Dijkstra算法更好？

After a lot of Googling, I've found that most sources say that the Dijkstra algorithm is "more efficient" than the Bellman-Ford algorithm. But under what circumstances is the Bellman-Ford algorithm better than the Dijkstra algorithm?

我知道更好是一个广义的说法，因此我特别指的是速度和空间（如果适用）。当然，在某些情况下，Bellman-Ford方法比Dijkstra方法更好。

I know "better" is a broad statement, so specifically I mean in terms of speed and also space if that applies. Surely there is some situation in which the Bellman-Ford approach is better than the Dijkstra approach.

推荐答案

Bellman-Ford算法是一种单源最短路径算法，因此当边缘权重为负时，它可以检测图形中的负周期。

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.

两者之间的唯一区别是Bellman Ford具有

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

来自维基

不过，Dijkstra的算法贪婪地选择了最小权重节点
尚未处理，并在其所有输出边缘上执行此放松过程
；相比之下，Bellman-Ford算法
只是放松了所有边缘，并且执行了| V |。 − 1次，其中| V |
是图中的顶点数。在每个重复中，具有正确计算距离的顶点数量从
增长，由此得出的结论是所有顶点最终都具有正确的
距离。 与Dijkstra相比，该方法允许将Bellman-Ford算法
应用于更广泛的输入类别。

$ b $但是，通常在没有负权重边缘的情况下更好地考虑b

Dijkstra，因为典型的二进制堆优先级队列实现具有O（（| E | + | V |）log | V |）时间复杂度[Fibonacci堆优先级队列给出O（| V | log | V | + | E |）]，而Bellman-Ford算法具有O（| V || E |）复杂度

Dijkstra is however generally considered better in the absence of negative weight edges, as a typical binary heap priority queue implementation has O((|E|+|V|)log|V|) time complexity [A Fibonacci heap priority queue gives O(|V|log|V| + |E|)], while the Bellman-Ford algorithm has O(|V||E|) complexity

这篇关于贝尔曼·福特vs迪克斯特拉：在什么情况下贝尔曼·福特更好？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！