一個新問題：一次要全部點對
前三篇指南回答的都是同一種形狀的問題：固定一個起點，找出從它到其他每個地方的最短路徑。那是單源最短路徑問題，而鬆弛解決了它——權重非負時用戴克斯特拉，有些權重為負時用貝爾曼-福特。但許多真實任務問的是更大的事：「每一對」頂點之間的最短距離。想像一張道路網，你想要所有城鎮之間完整的距離表；或是一個路由矩陣，每個節點都需要知道它到其他每個節點的成本。這就是全點對最短路徑問題，它值得擁有自己的演算法。
偷懶的答案是：把某個單源演算法跑 n 次，每次換一個頂點當源點。這行得通，而且在合適的圖上甚至是最好的方案——先記住這點，它會在強生演算法那裡回來。但從每個源點都跑一次貝爾曼-福特，要花 n 倍的 O(V*E)，在稠密圖上（此時 E 大約是 n^2）會爬升到 O(n^4)。對稠密圖來說這很浪費，而且更糟的是，它白白丟掉了全點對問題擁有、而單源問題沒有的一個優雅結構。弗洛伊德-沃歇爾恰恰利用了那個結構。
弗洛伊德-沃歇爾：中介頂點的想法
弗洛伊德-沃歇爾是一個動態規劃，而它全部的巧思就在於它用來建表的那個變數。把頂點編號為 1 到 n。現在定義一個子問題：從 i 到 j 的最短路徑是多少，如果這條路徑中途只准經過 {1, 2, ..., k} 這個集合裡的頂點？把這個距離記作 d(i, j, k)。兩個端點 i 與 j 永遠是允許的；限制純粹在於哪些頂點可以充當中途的踏腳石。我們要讓 k 從 0 一路長到 n，慢慢解鎖越來越多頂點作為可用的中介。
為什麼這是對的變數？因為它給出一個乾淨的遞迴關係式。考慮那條可使用 {1, ..., k} 中介、從 i 到 j 的最短路徑。它對頂點 k 的處置恰好只有兩種情形。要嘛這條路徑根本不用 k——那麼它只用到 {1, ..., k-1} 裡的中介，於是它的長度就是 d(i, j, k-1)。要嘛它確實用了 k，而且恰好一次（用兩次代表繞了一個經過 k 的環，在沒有負環時這永遠沒有幫助）。那麼這條路徑乾淨地拆成一段最佳的 i 到 k、再加一段最佳的 k 到 j，而這兩段各自又只准使用 {1, ..., k-1} 裡的中介。於是它的長度是 d(i, k, k-1) + d(k, j, k-1)。真正的答案就是這兩者中較小的那個。
d(i, j, 0) = weight(i, j) if edge i->j exists, else +infinity (and 0 if i == j)
d(i, j, k) = min( d(i, j, k-1), # path avoids vertex k
d(i, k, k-1) + d(k, j, k-1) # path routes through k
)把那個遞迴關係式變成一張由下而上的表，程式碼小得幾乎令人吃驚：三層巢狀迴圈，其中 k 在「最外層」，i 與 j 在裡面。最外層的 k 迴圈正是用來執行遞迴的相依關係——當你處理第 k 層時，等式右邊你讀到的每個項，都已在第 k-1 層定案了。靠一個聰明的就地技巧，你甚至可以拿掉第三個維度，原地更新單一張 n×n 的距離矩陣；可以證明覆寫是安全的，因為在第 k 輪期間，第 k 列與第 k 行的項並不會改變。結果就是整個演算法只需短短幾行。
為何正確、代價多少，以及一個免費的附贈
正確性是一個乾淨的、對 k 進行的數學歸納法。歸納假設是：在第 k 輪之後，每個項 d(i, j) 都等於「只使用 {1, ..., k} 中介」的真正最短 i 到 j 距離。基底 k = 0 成立，因為不准任何中介時唯一的路徑就是單一條邊，而那正是初始矩陣。歸納步驟就是我們剛做的情形分析：任何受限於 {1, ..., k} 的最短路徑，要嘛跳過 k（由舊值涵蓋），要嘛用 k 一次並在它那裡拆開（由那個和涵蓋），而兩者取最小值是正確的，這由套用到第 k-1 層的假設保證。當 k 抵達 n，所有頂點都成了可用中介，於是 d(i, j) 就是不受限的最短距離——正是我們想要的。
代價可以直接從迴圈讀出：三層巢狀迴圈各跑遍 n 個頂點，內層只做 O(1) 的工作，得到 Theta(n^3) 的時間。空間是 Theta(n^2)，用於那張距離矩陣（就地技巧拿掉了 k 維度）。注意一件令人鬆一口氣的事：執行時間完全不取決於邊的數量，而且它不在乎權重是否為負。同一個扁平的三層迴圈，對稀疏圖與稠密圖一視同仁。這種對邊數的不敏感，正是為什麼弗洛伊德-沃歇爾是稠密圖的自然選擇——當 E 已經接近 n^2 時，你反正也很難勝過 n^3，而你只用一趟整潔的掃描就拿到了每一對。
強生演算法：重新賦權，讓戴克斯特拉變合法
Theta(n^3) 對稠密圖沒問題，但在「稀疏」圖上就太過頭了。如果 E 遠小於 n^2——像一張每個城鎮只連到少數幾個鄰居的道路圖——我們會很想從 n 個源點各跑一次戴克斯特拉，因為每次戴克斯特拉只花 O(E log V)。那會得到 O(n*(E log V))，當 E 很小時遠低於 n^3。但麻煩既殘酷又熟悉：戴克斯特拉碰上負邊權重根本就是錯的。所以一旦出現哪怕只有一條負邊，把它跑 n 次的美夢就當場崩塌。強生演算法就是這個救援——它把所有權重變成非負，而不改變哪條路徑最短，然後才放出戴克斯特拉去跑 n 次。
天真的想法——「乾脆給每條邊都加上一個大常數，讓它們都不是負的」——是個經典陷阱，而且值得看清它究竟為何失敗。給每條邊加上常數 c，等於每條邊加 c，於是邊數較多的路徑被罰得比邊數較少的路徑更重。這會翻轉哪條路徑最短：一條又長又便宜的路徑可能輸給一條又短又貴的。強生的技巧更微妙。給每個「頂點」v 指派一個數字 h(v)，一個「位勢」或高度，並把每條邊 u 到 v 的權重從 w(u, v) 重新賦權為 w'(u, v) = w(u, v) + h(u) - h(v)。現在把任一條從 s 到 t 的路徑上的新權重加總：中途的那些 h 項會像望遠鏡一樣相消，只留下 total' = total + h(s) - h(t)。每一條 s 到 t 的路徑都平移了「相同」的量 h(s) - h(t)，所以它們之間的排序毫髮無傷——最短的依然最短。
所以任何位勢的選擇都保住最短路徑。剩下的魔法是選一個 h，使得每條重新賦權後的邊都非負，也就是 w(u, v) + h(u) - h(v) >= 0，移項後得到 h(v) <= h(u) + w(u, v)。這個不等式應該看起來無比眼熟：它正是最短路徑距離永遠滿足的三角不等式。所以如果我們讓 h(v) 等於從某個源點到 v 的最短距離，重新賦權就保證非負。強生演算法正是這麼做：加上一個全新的頂點 q，用權重為 0 的邊連到每個頂點，從 q 跑一次貝爾曼-福特，得到對所有 v 的 h(v) = dist(q, v)（之所以用貝爾曼-福特，是因為這些邊可能為負），然後把它們當作位勢。
- 加上一個虛設頂點 q，用權重為 0 的邊接到其他每個頂點；從 q 跑貝爾曼-福特。若它回報有負環，就停止——這個問題本身沒有良好定義。
- 對每個頂點 v 設 h(v) = dist(q, v)。這些位勢滿足三角不等式，因此它們會讓每條邊都變成非負。
- 重新賦權每條邊：w'(u, v) = w(u, v) + h(u) - h(v)。現在所有權重都非負，而最短路徑不變。
- 在重新賦權後的圖上，從 n 個頂點各跑一次戴克斯特拉。把每個結果換算回來：真正的 dist(u, v) = dist'(u, v) - h(u) + h(v)。
誠實地在兩者間做選擇
把強生的帳單加起來：一次貝爾曼-福特是 O(V*E)，接著 n 次戴克斯特拉、每次 O(E log V)，合計 O(V*E log V)。在 E 大約是 n 的稀疏圖上，這約為 O(n^2 log n)——舒舒服服地低於弗洛伊德-沃歇爾的 n^3。但在 E 大約是 n^2 的稠密圖上，強生退化到約 O(n^3 log n)，此時比弗洛伊德-沃歇爾還「差」了一個 log 因子，而且要寫對的程式碼多得多。所以誠實的經驗法則是：稀疏圖、可能有負邊，找強生；稠密圖，找弗洛伊德-沃歇爾。而如果權重本來就全部非負，你可以完全跳過強生的貝爾曼-福特前處理，直接把戴克斯特拉跑 n 次就好。
記得那個關於漸進的老生常談式誠實：這些是針對大圖的縮放定律，而非在每個規模上的定論。弗洛伊德-沃歇爾三層迴圈裡藏的常數因子很小——就是三個迴圈和一個 min——而強生要背負優先佇列、貝爾曼-福特，以及重新賦權的記帳開銷。在一張小的、或只是中等稀疏的圖上，簡單的 n^3 掃描很容易就贏過漸進上更快的強生。「在紙上更快」是關於增長的陳述，而不是對你那個特定輸入的保證。
退一步看見其中的統一。弗洛伊德-沃歇爾正面迎擊全點對問題，把它當成一個「以哪些中介頂點被允許」為變數的單一動態規劃——這是真正不同的想法，而不只是把鬆弛重複多次。強生則相反，是純粹的組合：它原封不動地重用前幾篇指南建好的貝爾曼-福特與戴克斯特拉，用一個變換把它們黏起來——這個變換把一張困難的圖（有負邊）變成一張容易的圖（非負），同時保住答案。那個「用位勢重新賦權」的技巧——讓每個量按每個頂點的高度平移，使望遠鏡式的相消清理掉結構——是一個深刻、可重用的想法，在最佳化的各處反覆出現。兩個演算法都值得帶著走：一個是自成一體的寶石，另一個是一堂「站在你已信賴的工具肩膀上」的大師課。