BellmanߝFord最短路径算法的性能
我用队列实现了 Bellman - Ford 算法的解决方案，并将其性能与 Dijkstra 算法进行了比较。 他们非常接近，这对我来说是一个惊喜，因为贝尔曼 - 福特的复杂性是 O(NM)。 我知道复杂性是针对最坏情况的，但结果仍然令人惊讶。 我搜索了一些关于 Bellman-Ford 的信息，只在 Sedgewick, Algorithms in Java 中找到了这样的说法“在真实网络上，Bellman-Ford 算法通常以线性时间运行”。 您能给我解释一下贝尔曼-福特算法的性能行为吗？
I implemented the solution of Bellman - Ford algorithm with a queue and I compared its performance with the Dijkstra algorithm. They were pretty close and that was a surprise for me because the complexity of Bellman - Ford is O(NM). I know that the complexity is for the worst case, but still the result was surprising. I searched for some information about Bellman - Ford and I found only this statement in Sedgewick, Algorithms in Java "on real networks the Bellman–Ford algorithm typically runs in linear time".
Could you give me an explanation of the Bellman - Ford algorithm performance behaviour?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这是一篇非常简单的论文（ PDF 链接）。
它还列出了伪代码和进一步的分析。
Here's a paper on it that's pretty straight forward (PDF Link).
It lists pseudocode and further analysis as well.