Bellman-Ford最短路径算法的性能
提问于 2009-06-15 08:40:04
我使用队列实现了Bellman - Ford算法的解决方案，并将其性能与Dijkstra算法进行了比较。他们非常接近，这对我来说是一个惊喜，因为贝尔曼-福特的复杂性是O(NM)。我知道复杂性是最坏的情况，但结果仍然是令人惊讶的。我搜索了一些关于贝尔曼-福特的信息，我只在Sedgewick中找到了这句话，算法在Java中“在真实的网络上，贝尔曼-福特算法通常在线性时间内运行”。你能给我解释一下贝尔曼-福特算法的性能行为吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2009-06-15 08:51:17
这里有一篇非常直接的论文(PDF Link)。
贝尔曼-福特算法的复杂性取决于边缘检查或松弛调用的数量。(注意，这与松弛步骤不同，松弛步骤指的是实际执行的更改。)如前所述，使用BGL实现时，松弛调用的数量可以小于|V ||E|。事实上，它比一般情况下的|V ||E|小得多。
它列出了伪代码和进一步的分析。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/997104
复制
腾讯云开发者
