SPFA演算法可否取代Dijkstra演算法成為計算單源最短路徑的最優解？

01-04

不可以

bellman-Ford演算法對於複雜度沒有保證。

不可以，有專門卡spfa而讓dijkstra過的數據。。而且帶堆dijkstra一般是比spfa快的

不可以。SPFA只是BellmanFord的一種優化，其複雜度是O(kE)，SPFA的提出者認為k很小，可以看作是常數（感謝 @Adder 指正），但事實上這一說法十分不嚴謹（原論文的「證明」竟然是靠編程驗證，甚至沒有說明編程驗證使用的數據是如何生成的），如其他答案所說的，在一些數據中，這個k可能會很大。而Dijkstra演算法在使用斐波那契堆優化的情況下複雜度是O(E+VlogV)。

SPFA，或者說BellmanFord及其各種優化（姜碧野的國家集訓隊論文就提到了一種棧的優化）的優勢更主要體現在能夠處理負權和判斷負環吧（BellmanFord可以找到負環，但SPFA只能判斷負環是否存在）。

p.s. 可以搜索一下原文《關於最短路徑的 SPFA 快速演算法》，作為一篇論文的嚴謹性實在不敢恭維。

SPFA 演算法遠遠沒有百度百科上吹的那麼好。

SPFA在稀疏圖上快，因為是通過邊來增廣的。

dijkstra在稠密圖上快。因為是通過點來增廣的。

某些情況下dijkstra 加上堆優化，在處理大數據的時候會比SPFA快很多；

但是SPFA在隨機數據的綜合表現中相比dijkstra優勢還是比較大的。

總而言之，各有所長。

不可以，這個得看圖是稠密圖還是稀疏圖，在以上兩種圖上兩種演算法各有優勢

SPFA在分層圖上容易被卡。。。畢竟就是個bfs。。。複雜度是沒法保證一直最優的。

不可以，演算法特性不同，適用情況不同

這種問題太天真太幼稚

印象中有 spfa killer (針對spfa生的測資)...

spfa最壞情況很差，一般不用，競賽用很好，很好編，也可以解決負環。

用斐波那契堆優化的Dijkstra快的飛起。