Bellman-Ford最短路径算法的性能

Question

我用队列实现了Bellman - Ford算法的解决方案,并将其性能与Dijkstra算法进行了比较.他们非常接近,这对我来说是一个惊喜,因为贝尔曼 - 福特的复杂性是O(NM).我知道复杂性是最坏的情况,但结果仍然令人惊讶.我搜索了有关Bellman - Ford的一些信息,我在Sedgewick中发现了这个声明,Java中的算法"在实际网络中,Bellman-Ford算法通常在线性时间内运行".你能给我一个贝尔曼 - 福特算法表现行为的解释吗？

Answer 1

这是一篇很简单的文章(PDF链接).

Bellman-Ford算法的复杂性取决于边缘检查或放松呼叫的数量.(注意,这与参考所执行的实际变化的放松步骤不同.)如上所述,松弛调用的数量可以小于| V || E |.与BGL实现.实际上,它比| V || E |小得多 在一般情况下.

它还列出了伪代码和进一步的分析.