本題為教學題所以很裸很水（但可能要小心處理負環傳遞）。
在圖論中，最基本的兩種經典題目是最小生成樹（Minimum Spanning Tree）與最短路徑（Shortest Path）這兩個問題，其中前者有兩個知名演算法 Kruskal's Algorithm 與 Prim's Algorithm，以及一個因為略難寫而顯為人知的 Borůvka's Algorithm。而後者大多人可能都只記得 Dijkstra's Algorithm，但卻忘記了 Bellman-Ford Algorithm 可能因為它的複雜度較差，不過或許有些人它的一個強大的改進版本，叫做 SPFA (Shortest-Path-Faster-Algorithm)，由於它簡單好寫又強大，因此也被廣泛應用於競賽界。本題將要來深入介紹 SPFA 這個演算法。
首先先來說明為什麼有需要這個演算法，在有複雜度良好（$O(E\log V)$ 或 $O(E+V\log V)$）的 Dijkstra's Algorithm 的情況下為什麼還需要其他演算法。這是因為 Dijkstra's Algorithm 有一個最大的缺點是：他不能跑在有負邊的圖上，否則結果會是錯的。因此對於有負邊的最短路徑問題，又或者是判斷一張圖是否有負環等這類的問題就不能使用 Dijkstra's Algorithm 了，此時便只能使用 Bellman-Ford 或 SPFA 了。本題將是一題裸的判斷負環的題目。
再來，既然 SPFA 源自於 Bellman-Ford，因此也先簡單介紹一下 Bellman-Ford 演算法。Bellman-Ford 演算法與 Dijkstra's Algorithm 相同都是基於用 relaxation 來不斷的降低起點到各個點之間的最短距離，並且可以一口氣求出起點到所有點的最短路徑。但不同的點在於 Dijkstra's Algorithm 是基於邊權非負這點，所以只要依照當前點的距離最小者來有小到大 relax 即可得到正確的答案。然而再有負全邊的情況下違反了它的假設因此會出錯。但可以注意到的是如果有一個正確的 relax 順序，那麼每個點其實只要依序各 relax 一次就能找到正確答案，只是礙於這個順序在有負權邊的情況下不易找到。因此 Bellman-Ford 的想法便是暴力的依序對每個點都 relax 點的數量次$- 1$，那麼就能包含到所有可能的 relax 順序所以一定能找到最佳解。不過當然的，成本便會是 $O(VE)$ 因為要對所有 $E$ 條邊都 relax $V-1$ 次。
最後則是要來介紹這題的重點 SPFA。可以注意到 Dijkstra's 演算法在特殊情況下直接找出正確的 relax 順序，而 Bellman-Ford 又相反過於保守的枚舉了所有情況，但實際上像必是又多判了非常多多於的情況。例如可以想像若一個點在某一輪並沒有被 relax，那麼他的距離值沒有被改變所以在下一輪也不可能可以 relax 其他人。基於這個明顯可以優化的點的考量，於是有了 Bellman-Ford 的改進版 SPFA 的出現。SPFA 在實做上與 Bellman-Ford 有很大的區別，為了好好善用前述觀察，SPFA 不再是以迴圈式的執行指定輪數，而是改以用一個 queue 維護「有被 relax 而需要再考慮 relax 其他點的點集合」。一開始只有起點在集合中，之後不斷的重複執行， 每次從 queue 中拿出一個點來嘗試對所有其他點 relax，如果一個點被成功 relax 了，那麼就將它丟進 queue 中準備嘗試拿來 relax 其他點。當然，一個點同時被丟進 queue 中是沒有意義的，因此會額外用個 bool 陣列來維護目前在 queue 中的點，當要把一個點加進 queue 時如果該點早已在 queue 中了當然就不要再重複放進去了。不斷地重複這個流程直到 queue 中沒有點了代表都 relax 到一個穩定狀態，演算法就結束了。以上便是經典的 SPFA 演算法，雖然其理論最差複雜度仍與 Bellman-Ford 相同，但上述 heuristic 的優化卻往往能壓掉非常大量多餘的 relaxation。實際上 SPFA 在絕大多數的圖都跑得極快，甚至通常都跑得比 Dijkstra's Algorithm 還要快在競賽中過關斬將，甚至有些人覺得這比較好寫連一般沒有負邊的最短路徑問題都選擇寫 SPFA，也因此在競賽界甚至被號稱為線性複雜度（實際上他在隨機圖中真的是期望線性複雜度）。
除此之外，雖然原本的 SPFA 就足以快到以近於 Dijkstra's Algorithm 的速度通過幾乎的題目了，然而他甚至還有額外的簡單優化技巧讓其實務效率更勝之前，執行時間通常甚至能遠低於原版或 Dijkstra's Algorithm。其中第一個優化技巧是基於距離越進的點越容易能成功 relax 其他點（可能可以想像就如同 Dijkstra's Algorithm 那樣），因此實做上會選擇把 queue 換成 deque，並在每次要提出一個點來做 relax 時，會比較 deque 頭尾兩個點的距離，並選擇較小者來執行。而另一種優化則是考慮到假設一個點 $x$ 在上一次是被點 $p$ relax 的（換句話說在目前找到的最短路徑中 $p$ 是 $x$ 的父節點），那麼可想而知如果 $p$ 被 relax 了，$x$ 畢竟也會再之後跟著一起被 relax。因此實做上便是額外開一個陣列在 relax 時紀錄每個點的父節點，然後在每次一個節點被提出來執行 relaxation 時，如果該節點的父親已經在 queue 中了，那麼便直接跳過當前的程序因為既然該點之後還會在其父親 relax 時被降低距離，本輪作的 relax 一定也會在之後被再次 relax ，因此不用現在重複做一次。可以注意到的是本身 SPFA 的實做就有維護點是否在 queue 中，而多紀錄父節點也有好處例如可以拿來找出最短路徑或蓋出最短路徑樹等，也是常見的應用。另外，這兩個優化並不衝突也是可以同時使用的，雖然往往其中一個的優化就足以快到接近線性壓不下去了。
本題是裸的找負環的題目，也就是說無法使用 Dijkstra's 演算法。順帶一題，SPFA 在找負環的題目中還有額外的優化可以做。因為與 Bellman-Ford 每個點的 relax 次數在每輪迴圈都是相同的，SPFA 每個點有各自的 relax 次數，雖然這裡要說的不是次數。實際上 relax $V-1$ 次可以找到正確的解也可以想像成是因為 Bellman-Ford 中 relax $i$ 次後可以找出所有長度不超過 $i+1$ 的最短路徑，那麼 relax $V-1$ 次就能找出長度不超過 $V$ 的最短路徑，也就是所有情況都被考慮進去了因此會是最佳解。如果在之後還發現可以 relax 那麼根據鴿籠原理路徑中必定有出現環，而且是負環否則把環拆掉的路徑一定比較短，不可能可以成功 relax。因此對比到 SPFA 時，可以額外在開一個陣列維護每條路徑的長度，維護方法當然是簡單的一開始將起點設成 $1$，若點 $x$ 是被點 $p$ relax 的（i.e. $p$ 是 $x$ 的父親），那麼點 $x$ 的路徑長當然就是點 $p$ 的路徑長$+1$。當發現 relax 出一個路徑長是 $V+1$ 的點時便能斷定圖中存在負環，會比每個點要更新該次數快很多達成。可以注意到這個剪枝技巧與前述第一種優化技巧非常合拍，往往又能產生非常大的效能優化。歡迎各位在本題練習各種方法。
注意：本題為了區分各種作法因此有卡一點常數（標程 1s 而 TL 1.5s），請各位努力優化程式xd。（不過實際上最佳作法與次佳仍有一定的時間差所以不算卡到太緊，且標程作法不超出上述範圍（雖然我的 code 常自帶小常數），所以不用考慮到太毒太奇怪的作法。）
5/8 更：有篇最近才新出爐的論文提出了真正 near-linear time 演算法來找出帶負權邊的最短路徑問題，有興趣的人可以去拜讀 https://arxiv.org/abs/2203.03456 ，不過在正常範圍實務上仍是以 Bellman-Ford 或 SPFA 較優，畢竟這種新的論文演算法通常偏胖也難寫很多。
第一行有 3 個正整數 $n,m,s$ 分別代表點的數量、邊的數量、與起點編號。
接下來有 $m$ 行每行有 3 個整數 $x,y,w$ 代表圖中有一條有向邊從點 $x$ 到點 $y$ 權重為 $w$ 的邊。
- $1\le n\le 20000$
- $0\le m\le 20000$
- $1\le s,x,y\le n$
- $x\ne y$
- $-10^9\le w\le 10^9$
輸出一行共 $n$ 個整數（以空白分隔，不得有行尾空白），第 $i$ 個整數為從起點 $s$ 走到點 $i$ 的最短路徑權重。如果該點無法從起點走到則輸出 998244353998244353。如果起點到該點的路徑上存在負環則輸出 -998244353998244353。
# 範例測資 1 5 8 4 4 1 4 1 3 -4 2 1 5 1 5 -5 2 4 5 5 3 0 2 5 -4 4 5 -1 # 範例測資 2 10 15 4 7 1 -8 1 8 -10 2 9 -1 6 2 4 6 9 -2 8 2 1 9 8 -9 5 2 -9 3 8 4 7 4 -2 9 1 10 10 5 -6 4 8 8 5 3 -3 4 10 0
# 範例測資 1 4 998244353998244353 -1 0 -1 # 範例測資 2 -998244353998244353 -998244353998244353 -9 0 -6 998244353998244353 998244353998244353 -998244353998244353 -998244353998244353 0
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||