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

Question

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

Answer 1

这里有一篇非常直接的论文(PDF Link)。

贝尔曼-福特算法的复杂性取决于边缘检查或松弛调用的数量。(注意，这与松弛步骤不同，松弛步骤指的是实际执行的更改。)如前所述，使用BGL实现时，松弛调用的数量可以小于|V ||E|。事实上，它比一般情况下的|V ||E|小得多。

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