帶負權的無負環最短路問題

對于一張有負邊權的圖，普通 Dijkstra 就不能用了，比如：

正常的 Dijkstra 擴散的節點依次為 $1,3,2,4$。
這時候可以發現，當點 $2$ 擴散的時候，原本達到點 $3$ 的路徑長度是 $1$，路徑 $1?2?3$ 的權值之和為 $?2$，明顯更短，這個時候點$1$ 到點 $3$ 的路徑長度就會被更新為 $?2$，但是，點 $3$ 在點 $2$ 之前已經被擴散過，不會在進行第二次擴散。此時，點 $1$ 到點 $4$ 的路徑長度依舊是 $1+2=3$。

這里說明了 Dijkstra 的一個缺陷，貪心思路會考慮不到后續的負數。

那么，我們可以對 Dijkstra 做一個改動，解決現在遇到的問題。
上述的問題發生的根源就是 $vis$ 數組，在當前點找到更優值的時 $vis$ 數組不會改變，就導致了上圖中點 $4$ 沒有被更新，所以我們在找到更優值時就再給當前點一個機會。

if(dis[y]>dis[x]+z){vis[y]=0;dis[y]=dis[x]+z;
}

這樣可以很好地解決上圖中出現的問題，但是判斷負環還是需要 SPFA
那么，我們將上述的改動版 Dijkstra 命名為SPstra

帶負環的最短路問題

這個時候就可以考慮用到 SPFA。
SPFA 與 Dijkstra 的不同點：

入隊條件

Dijkstra 的遍歷概念是：擴散
而 SPFA 的遍歷概念是：挑選
SPFA 的標記表示的是“是否在隊列中”，也就是說有沒有看過這個元素值更新后對相連點的影響。
如果沒有在隊列中，并且還找到了當前點更優的方案，那么當前點就該入隊上班了。（可以借助文章最頂上的圖來理解）。

出隊標記

出隊后，元素就不在隊列中了，標記取消。

負環判斷

負環是什么？
負環就是一個有向圖中的環，并且對這個環遍歷一圈得到的權值總和為負，那么這個時候就可以一直繞著這個環轉圈圈，使權值總和越來越小。
我們假設：一張有 $n$ 個點的有向圖中有這樣一個點 $x$，這個點十分有魅力，圖中其余的 $n?1$ 個點都有一條邊連向這個點。

再極端一點，這其余的 $n?1$ 個點按照被遍歷到的順序依次對點 $x$ 有更優貢獻。
那么，這個點就會被入隊 $n?1$ 次，這個時候還沒有出現負環。
但是，如果這個點再被入隊一次，入隊次數達到了 $n$ 次，就一定有一個點（暫且稱為點 $y$）連接點 $x$ 的這條路徑被遍歷了兩次，這個時候就有了負環，因為點 $x$ 在被點 $y$ 連接的情況下還有一條負數邊權和的路徑連接著點 $y$。

SPFA 可否使用優先隊列優化

其實使用優先隊列優化的 SPFA 就是前面的 “SPstra” 加上一個負環判斷。

對于這個問題，答案是：能，但是很極端。

SPFA 優先隊列優化的適用場景

對于正邊權居多的圖，可以使用優先隊列優化，這樣可以使效率接近 Dijkstra 的 $O(N\log N)$。

普通 SPFA 的適用場景

對于負邊權居多的圖，其實普通隊列和優先隊列的遍歷次數都是差不多的，只是順序變了，而且優先隊列還多了一個 $O(\log N)$，效率還不如普通隊列。

總結

考試或者比賽時，題目的數據我們無從得知。
但我們知道的是，造數據的人們都是陰險狡詐忠懇善良的，我們可以猜疑相信他們。