贝尔曼-福德最短路径算法的性能

Question

我用队列实现了Bellman-Ford算法的解决方案，并将其与Dijkstra算法进行了性能比较。它们的表现非常接近，这让我感到惊讶，因为Bellman-Ford的复杂度是O(NM)。我知道这个复杂度是针对最坏情况的，但结果仍然令人惊讶。我搜索了一些关于Bellman-Ford的信息，在Sedgewick的《Java算法》中只找到了这样一个说法：“在真实网络中，Bellman-Ford算法通常以线性时间运行”。

你能给我解释一下Bellman-Ford算法的性能行为吗？

- Ionel Bratianu

---

如果您正在寻找C++中这两种算法的良好实现，请查看Boost图形库。 http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/table_of_contents.html - RED SOFT ADAIR

代码在这里：https://github.com/boostorg/graph/blob/develop/include/boost/graph/bellman_ford_shortest_paths.hpp - assylias

Answer 1

这里有一篇关于它的论文，非常简单明了（PDF链接）。

Bellman-Ford算法的复杂度取决于边缘检查或松弛调用的数量。（请注意，这与实际执行的更改所涉及的松弛步骤不同）。如上所述，在BGL实现中，松弛调用的数量可能小于|V||E|。事实上，在平均情况下，它比|V||E|要小得多。它列出了伪代码和进一步的分析。

- JP Alioto