问题描述
经过大量的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.
来自
$ 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迪克斯特拉：在什么情况下贝尔曼·福特更好？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！