如何看待 SPFA 演算法已死這種說法？
NOI2018 Day 1，T1 出題人卡了 SPFA 並在講課時說其死了。
我極其反對使用 SPFA 來用一個假複雜度頂替 Bellman-Ford 的名字，因此我曾試圖卡掉所有 SPFA 以及相關的優化，並且證明 SPFA 真的不行。
不過我遇到了一點小麻煩，還請有興趣的諸位幫幫忙。(UPD：Hacked，出現過的大部分 SPFA 都死完了）
顯然，普通 SPFA 是非常好卡的，只需要一個隨機網格圖（在網格圖中走錯一次路可能導致很高的額外開銷），或者一個構造過的鏈套菊花（使得隊列更新菊花的次數非常高）即可。很多奇怪寫法的 SPFA 都只能通過兩者中的至多一種，因此你只需要將圖構造為網格套菊花即可。
對於我知道的其他比較著名或者比較有效的優化：
LLL 優化：每次將入隊結點距離和隊內距離平均值比較，如果更大則插入至隊尾。
Hack：向 1 連接一條權值巨大的邊，這樣 LLL 就失效了。
SLF 優化：每次將入隊結點距離和隊首比較，如果更大則插入至隊尾。
Hack：使用鏈套菊花的方法，在鏈上用幾個並列在一起的小邊權邊就能欺騙演算法多次進入菊花。
SLF 帶容錯：每次將入隊結點距離和隊首比較，如果比隊首大超過一定值則插入至隊尾。
Hack：如果邊權之和很小的話似乎沒有什麼很好的辦法，因為令邊權之和為 ，那麼令容錯值為
，總複雜度似乎接近
。我不確定這個複雜度對不對，但是 SPFA 確實在邊權和小的時候跑得蠻不錯的。所以卡法是卡 SLF 的做法，並開大邊權，總和最好超過
。
mcfx 優化（thanks to @mcfx and @yfzcsc）：在第 次訪問一個結點時，將其放入隊首，否則放入隊尾。通常取
。
Hack：網格圖表現優秀，但是菊花圖表現很差。
P.S. 此優化與 SLF 帶容錯一起使用有更好的效果，可以使所需要的邊權上升許多。
@rafficas NTR：詳見 如何卡spfa？ - raffica的回答 - 知乎 。
Hack：菊花圖表現很差。
SLF + swap：每當隊列改變時，如果隊首距離大於隊尾，則交換首尾。
這個 SLF 看起來很弱，但卻通過了所有 Hack 數據。而且，非常難卡。
還請各位認為 SPFA 必死的爺爺們，來親手殺死這個苟延殘喘的 SLF 吧。
UPD: Hacked by @negiizhao and @鍾子謙。
Hack: 與卡 SLF 類似，外掛誘導節點即可。（是我菜了）
其實從原理上分析，所有 spfa 的優化都是為了使隊列接近優先隊列。然而，我們知道維護一個優先隊列在目前來說是需要 log 的複雜度的，所以低於該複雜度的 一定能 Hack。
屬實。
在非負邊權的圖中，隨手卡 SPFA 已是業界常識。在負邊權的圖中，不把 SPFA 卡到最慢就設定時限是非常不負責任的行為，而卡到最慢就意味著 SPFA 和傳統 Bellman Ford 演算法的時間效率類似，而後者的實現難度遠低於前者。
SPFA 的受到懷疑和最終消亡，是 OI 界水平普遍提高、命題規範完善和出題人的使命感和責任心增強的最好見證。
Update：
為了激勵並推廣卡 SPFA 這一行為，我提供一種最簡單的卡 SPFA 的方法（同時適用於有向圖和無向圖）：
Step 1 生成一棵以起點為根的樹，樹高盡量高（比如 1 為起點時，可以令每個點 i 的父親在 max(i-5,1) 到 i-1 隨機），邊權隨機，作為最短路徑樹，同時直接遞推求出每個點的帶權深度 d(i)
Step 2 對於剩下的邊，端點 (a, b) 隨機，邊權在 |d(b)-d(a)| 到 |d(b)-d(a)|+5 隨機（如果是有向圖則去掉絕對值符號，5 可以換成其他較小的正數）
這樣生成的圖中，次短路的條數非常的多，而 SPFA 一旦錯誤地進入了次短路的分支，就會使得一整棵子樹被賦錯誤的距離，從而在後期不得不重新更新。而由於邊權接近，剪枝的效果會受到很大影響。
這個生成方法代碼簡單易寫，只需要大量的隨機，不需要構造網格等特殊結構，生成器中甚至不需要建圖 ，適合所有有責任心的出題人使用。
在決大部分費用流問題上SPFA還是好用的啊..
建圖是特殊圖，有些題還不知道 SPFA 能不能被卡..
如果你知道正確的 SPFA 判負環的姿勢，在寫消圈的時候會快上不少..
（當然消圈也能被替代就是了..
當然正權圖用 SPFA 就是在作死.. 負權圖感覺還是有點用的吧（反正代碼長度和 Bellman-Ford 也差不多
好啊
這樣如果有人覺得費用流用Johnson的方法消除負權，再跑Dijkstra不優美的話，就會去學網路單純形了，然後就可以推廣網路單純形及其動態樹優化了，然後就會有人深入瞭解動態樹了，然後大家就都會用top tree代替樹分治了。而這一切會加速OI演算法工業化進程，促進OI嚴謹化、知識點體系化，把OI推向更高的平臺。
題目保證了沒有負權邊，為什麼不用堆優化的 Dijkstra 呢？
推薦閱讀：
