Bellman_Ford求调！

DragonForge @ 2024-06-29 16:34:56

by Lyrith_with_xQ @ 2024-06-29 16:39:30

Bellman ford慢啊，是 O(nm) 的，所以会T

by Lyrith_with_xQ @ 2024-06-29 16:42:00

建议不要用bellman ford，去学学SPFA和Dijkstra吧，复杂度是 O(n \log n) 和 O(Kn) 的

by masonxiong @ 2024-06-29 17:30:50

@CSP_Alex_juruo

az，我认为 “Bellman Ford 速度最慢”这件事情应当是一个常识吧，下面是常用单源最短路算法的时间对比：

• Dijkstra: O(n\log n+m)（使用 Fib 堆）
• SPFA: O(kn)（k 是一个神奇常数，平均值为 2，最差为 n）
• Bellman Ford: O(nm)

可见，Bellman Ford 基本完全劣于 SPFA，因为后者的最差时间复杂度是前者的最好时间复杂度

更何况，卡 Bellman Ford 的方法非常简单：一张完全图就可以卡死了，因为此时 m=O(n^2)，Bellman Ford 的复杂度变为 O(n^3)

by DragonForge @ 2024-07-07 17:12:50