弗洛伊德-沃舍爾演算法（Floyd-Warshall algorithm）
/ FLOYD WAR-shall /
弗洛伊德-沃舍爾用電腦科學中最優雅的短程式之一填滿整張全源距離表：三層巢狀迴圈。其想法是逐步擴大你被允許經過的城市集合。先找出不經任何中繼城市的最佳路線，再找允許經過城市 1 的路線，接著允許經過城市 1 或 2 的，依此類推。每當你多准許一個城市作為停靠點，你就問：經過它是否縮短了任一對的距離。
維護一個矩陣 D，D[i][j] 是目前從 i 到 j 的最佳距離，初始化為直接邊權（或無限大，對角線為 0）。然後讓 k 從 1 跑到 V，內部對所有 i 與所有 j 套用單一更新 D[i][j] = min(D[i][j], D[i][k] + D[k][j])。外層索引的意義是一種動態規劃的分層：在某個 k 的迭代之後，D[i][j] 是從 i 到 j、只用取自 {1, ..., k} 的中繼頂點的最短路徑。歸納很乾淨——對下一個 k+1，任何用到至多 k+1 的中繼的路徑，要嘛避開 k+1（已計入），要嘛經過它一次，拆成 i 到 (k+1) 與 (k+1) 到 j 兩段，這兩段只用更早的中繼，正是被相加的那兩項。當 k 到達 V，每個頂點都是允許的停靠點，D 即持有真正的最短距離。成本是乾淨的時間 O(V^3)、空間 O(V^2)。
它的魅力在於簡潔與通用：寥寥數行，毫無問題地處理負權邊，且一次算出每一對，這就是它在小型稠密圖與競技程式設計中備受青睞的原因。它也偵測負環——若任一對角線條目 D[i][i] 變為負，就有一個負環穿過 i。誠實的限制：O(V^3) 對大型稀疏圖太慢（約翰森的 V 次戴克斯特拉在那裡勝出），且它需要完整的 V^2 矩陣存在記憶體中，故無法擴展到數百萬個頂點。
三個頂點，邊為 1->2 (4)、1->3 (11)、2->3 (2)。起初 D[1][3] = 11。當 k = 2（允許頂點 2 作停靠）：D[1][3] = min(11, D[1][2] + D[2][3]) = min(11, 4 + 2) = 6。對每個 k 執行的那一行 min(D[i][j], D[i][k] + D[k][j]) 就修好整張表。
索引 k 是一層 DP：在 k 迴圈之後，D[i][j] 是只用 {1..k} 中繼的最佳路徑。
迴圈順序很要緊：k 必須是最外層。把 i 或 j 放到 k 之外會算出錯誤的距離，因為對允許中繼的 DP 分層會被破壞。