如何卡spfa？

1.oi比賽寫spfa（不加優化）靠不靠譜？

2.會不會被「良心」出題人針對？

3.被針對的話是不是要乖乖寫dijkstra

4.spfa的時間複雜度是多少

不請自來。

1.oi比賽寫spfa（不加優化）靠不靠譜？

不靠譜

2.會不會被「良心」出題人針對？

會，卡的辦法是弄個網格圖

3.被針對的話是不是要乖乖寫dijkstra

對，不過不如嘗試以下奇怪的方法來避免被卡：（原創！）

維護一個叫臨時最短路樹的東西，剛開始只有一個源節點

這SPFA的過程中，每次鬆弛(u, v)邊時將v的父親設為u；v是有可能有後代的，所以將其所有後代的對應inqueue標記清除；在SPFA過程中如果發現隊頭節點的inqueue為空那麼跳過。理由是如果我們能鬆弛(u, v)邊，那麼從(u, v)走勢必比以前走過的那種走法好。將這個步驟稱為NTR。

inline int SPFA() {
int i, j, x, cnt = 0;
queue& Q;
memset(d, 0x3f, sizeof(d));
d[S] = 0;
Q.push(S);
setv(S, 1);
while(!Q.empty()) {
x = Q.front();
Q.pop();
cnt ++;
if(!query(x)) continue;
for(i = 0;i &< G[x].size();i ++) { Edge e = edge[G[x][i]]; if(d[x] + e.w &< d[e.v]) { d[e.v] = d[x] + e.w; Q.push(e.v); setc(e.v, 0); setv(e.v, 1); if(lca(e.v, x) == e.v) { return 0; } int f = getfa(e.v); linkcut(f, e.v, x); } } } return 1; }

以上為用lct實現的這東西的代碼的一部分（當時在測試lct模板 事實上正常來講用lct反而更慢

當有負權環時這個演算法也會出現環，所以可以用來快速找環。

只要隨機一下邊表順序，這個演算法就不會被奇怪的圖卡掉。當然對於網格圖不用隨機邊表順序也不會被卡。(迫真)(不信你們可以試看看...)

4.spfa的時間複雜度是多少

最壞時間複雜度為O(mn)

下面來證明期望時間複雜度的一個上界（作為期望的隨機因素為邊表的兩邊的端點號和邊的長度）

原創證明。確認以前沒人證明過。

放結論在前面：SPFA總的期望時間複雜度為O(nlognlog(m/n) + m)

看懂下面的前提是你看懂了上面第三題的解釋

最終的最短路樹一定有n-1條邊，則每個點平均有(2n-2)/(n)個出度，即2個出度。

然後顯然這個最短路樹的高度為O(logn)

臨時最短路樹的高度也顯然是O(logn)

那麼假如這個過程中不存在NTR，則時間複雜度為O(m+n)

如果存在NTR，那麼一次NTR的時間複雜度可以看成是O(logn)，因為多走了一個樹的高度次的鬆弛。

那麼期望存在NTR的次數是多少呢？

如果一個節點uNTR了另一個節點v，那麼設這個NTR後 對這個u還要再NTR幾次的期望為P(u)

有P(u)=log(出度)=log(m/n)，

那麼一個節點NTR的次數期望為O(log(m/n))

那麼NTR的總時間複雜度=O(logn) * O(log(m/n)) * O(n)=O(nlognlog(m/n))

很好這是一個上界...可以看出的確跟圖的稠密度有關

加起來，SPFA總的期望時間複雜度為O(nlognlog(m/n) + m)

那麼為什麼網格圖SPFA慢呢？？？為什麼我原創的演算法改進不會被網格圖卡呢？？？

因為SPFA在網格圖中這個臨時最短路樹的高度特別高(O(n))，NTR次數為O(n/logn)。SPFA在每次NTR時消耗的時間量是O(n)（3.10修正說法 消耗的時間為對應的子樹在演算法結束時的高度），而用我的演算法改進的話每次NTR消耗的時間量為鬆弛的v節點對應的這個子樹的高度（3.10修正說法 為v節點對應的子樹在對應的時間時有的子樹的高度），為O(logn)；

我的演算法來找負權環的期望時間複雜度也是O(nlognlog(m/n) + m)，但SPFA就是O(mn)了

我這演算法能不能被卡掉呢？當然能...卡掉的方法是菊花圖+刁鑽的訪問順序

更新 我想到了一種萬能的卡法 能把我的所有的解決方案卡成O(m根號m)的。無論怎麼拆菊花都無效。無論用不用優先隊列都無效。如果這麼出題的話那真的喪心病狂...我只能說拜託了我都證明了SPFA的期望時間複雜度了就別卡SPFA了（苦笑）如果要解決這個問題 除非能讓一個點所有的入度的鬆弛的順序是不由原圖決定的。如果能保證有這個條件我們就有和圖結構無關的期望O(mlognlogn)最短路演算法了。當然 也能找到入度最多的幾個菊花，然後等到這幾個菊花的入度的最短路值都得出來了再處理這些菊花，但是我還沒想到怎麼做這個...

樓下回答中的俄羅斯的卡SPFA方法我在想到這個演算法時就考慮過了，事實上我是獨立想到這個卡SPFA的辦法後對這個演算法的改進有了靈感的。因此樓下的辦法不僅卡不掉我的演算法，而且我的演算法跑起來還特別快（笑）

如果是隨機圖的話還是直接寫原版SPFA吧。

歡迎使用，如果實戰沒問題的話我說不定可以發篇論文呢2333

如果有錯誤歡迎指出。

SPFA 的複雜度是多項式的，複雜度 O(|V||E|)。

OI 比賽中，如果圖的 |V||E| 不大（例如 |V| &<= 1000，|E| &<= 10000），使用 SPFA 是靠譜的，而如果 |V||E| 較大（如 |V| &<= 50000，|E| &<= 100000），那麼 SPFA 可能就 TLE 了。

如果邊權非負，建議使用複雜度穩定的 Dijkstra。但有負權邊的時候 Dijkstra 不能用，只能用 SPFA。

卡SPFA似乎是需要按照特定的邊的訪問順序(對付網格圖無效)，一般來講隨機shuffle一下邊能避免一些極端的hack，不過較大規模的圖上SPFA效率確實不高.

順帶一個毛子的hack圖:http://codeforces.com/blog/entry/3730

blog.csdn.net

yfzcsc這位叉人之神的博客

1.在大多數比賽中，把一個問題轉化為最短路問題要比寫一個最短路的程序難的多所以基本不會卡

spfa非卡的話大概主要是在一些可以hack的OJ上。考試的時候如果為了趕時間寫個spfa無傷大雅

2.怎麼卡？大概畫完了是個網格一樣的東西，反正就是你讓你個好久以前更新的點被重新更新就會很傷

3.我個人除了卡rank基本不寫dijkstra，主要原因是對不開O2的比賽中STL的效率不滿意自己也懶不喜歡手寫堆比較累。一個比較好的方法就是你加邊到最後把邊表random一下這樣能解決不少問題

或者用一個什麼優化比如dis小的加前面dis大的加後面，反正只要你的邊表和他不一樣他就基本卡不住你

4.極限情況下就是沒優化的複雜度