我用队列实现了 Bellman - Ford 算法的解决方案，并将其性能与 Dijkstra 算法进行了比较。它们非常接近，这对我来说是一个惊喜，因为 Bellman - Ford 的复杂性是 O(NM)。我知道复杂性是针对最坏情况的，但结果仍然令人惊讶。我搜索了有关 Bellman - Ford 的一些信息，但我在 Sedgewick，Java 中的算法中只找到了这句话“在真实网络上，Bellman-Ford 算法通常在线性时间内运行”。你能给我解释一下贝尔曼 - 福特算法的性能行为吗？
问问题
3909 次
1 回答
5
这是一篇非常简单的论文（PDF链接）。
Bellman-Ford 算法的复杂性取决于边缘检查或松弛调用的数量。（注意这与松弛步骤不同，松弛步骤指的是实际执行的更改。）如前所述，松弛调用的数量可以小于 |V ||E| 使用 BGL 实现。事实上，它比|V ||E|小很多。在平均情况下。
它还列出了伪代码和进一步的分析。
于 2009-06-15T16:51:16.510 回答