為什麼在SPFA演算法中，判斷負權迴路的條件是任一節點進隊次數超過總結點數？

01-04

SPFA實是Bellmon-Ford最短路演算法的隊列優化版本，而通過進隊次數來判斷是否存在負環，實際上是利用了Bellmon-Ford演算法的性質，所以要先弄清楚Bellmon-Ford

沒有負環的Bellmon-Ford

我們考慮一個不包含負環的圖 $G=(V,E)$

演算法的想法非常簡單，進行 $|V|-1$ 次操作，每次操作對所有的邊鬆弛。

鬆弛可以形象的理解為更新當前最短路值，比如有一條從點 $u$ 到點 $v$ 的邊，如果點 $u$ 上的值加上邊的長度小於點 $v$ 上的值，那麼就更新點 $v$ 上的值（換句話說，存在一條從起點到 $u$ 再到 $v$ 的路徑，要比之前從起點到 $v$ 的路徑更短）。

為什麼這樣做是對的呢？我們可以回顧整個過程，第一次操作，我們一定能將起點 $s$ 的鄰居 $N(s)$ 中的某一個點更新為真正的最短路值（這個點以後不會被更新），關於這裡可以用反證法證明：

如果 $N(s)$ 中沒有一個點是更新完畢的，而 $u$ 是離 $s$ 最近的鄰居，那麼必然存在一條比 $s$ 直接到 $u$ 更短的路徑，與假設矛盾。

用同樣的道理，容易證明，每次我們至少能確定一個點被更新成了真正的最短路值（這個證明只需要將起點看作是個集合，將每次確定好的點加入起點集合即可），所以總共需要 $|V|-1$ 次（起點不用更新）。

下面來個圖解：

下圖中，從 $s$ 到 $u$ 的距離最近，第一操作的時候，如果 $u$ 沒有被更新成2，那麼也就是說存在類似紅色或者綠色這樣的路徑，比藍色更短，這是顯然不對的，所以第一次鬆弛就一定能把 $u$ 更新為真正的最短路值。

現在我們不妨來考慮一下，有負環的Bellmon-Ford會怎麼影響剛剛的證明。

如果有負環，那麼每次我們便不能說，我們已經確定了一個點，處於真正的最短路，這是因為，完全可以通過在負環上繞上幾圈，來達到更短的目的，即推翻了那個證明。

比如下圖，存在從 $s$ 到 $w$ 再到 $u$ 再到 $s$ 的負環，那麼這時候 $dis(u)=2$ 顯然不是最短路。

沒有負環時，我們知道，只需要 $|V|-1$ 次，就能確定所有點都被更新好了（每次至少更新好一個點），那麼如果存在負環， $|V|-1$ 次時，顯然時沒有更新好的，因為可以通過負環得到更短的最短路。由此就能得出結論：

如果操作次數超過 $|V|-1$ 次，那麼存在負環。

SPFA用隊列很大程度上優化掉了了Bellmon-Ford每次操作時的冗餘鬆弛，使得複雜度大大降低，但是本質上還是Bellmon-Ford。

所以一個點如果被加入隊列兩次，本質上等價於，這個點在Bellmon-ford中被操作了兩次。所以如果一個點被更新了|V|-1，則存在負環。

我記得之前還看過另外一種如果判一個一個點的進隊如果只存在一個簡單負環最多可能要跑n次這個環所以我們可以用從起點這個點之前的路徑總數&>n這樣只用跑一次環會稍微快一點

至於題主的問題我一般是這樣理解的對於一個完全圖最多有n-1個點能到第n個點所以當進隊大於n-1次就說明有負環至於為什麼是＞n是因為對於一個節點時候如果還是&>n－1那麼任意一個單節點的圖會被判定為存在負環綜合考慮取&>n

蒟蒻來答一波，有可能是口胡TAT。

說說我的想法：SPFA實際上還是一個Bfs的過程。當一個點u被加入隊列時，說明這次S到u的邊數比上次至少多一。如果S到u的最短路是大於等於n條邊的，說明存在負環