Floyd-Warshall 全對最短路

🎯 什麼情境該想到我

當你「要一次算出所有點對之間的最短距離，而且點數不多（$V\lesssim 500$）」的時候。
★ 它只有五行，是所有圖論演算法裡程式碼最短的——但那三層迴圈的順序只有一種是對的，而且寫錯不會報錯。

⚙️ 怎麼用（機制與推導）

核心：以「允許經過哪些中繼點」為階段的 DP

狀態定義：
$d^{(k)}[i][j]=\text{只允許用 }\{1,2,\dots ,k\}\text{ 當中繼點時，}i\to j\text{ 的最短距離}$

轉移：考慮「要不要經過 $k$」
$d^{(k)}[i][j]=\min (\underset{\text{不經過 }k}{\underbrace{d^{(k-1)}[i][j]}},\underset{\text{經過 }k}{\underbrace{d^{(k-1)}[i][k]+d^{(k-1)}[k][j]}})$

邊界：$d^{(0)}[i][j]=$ 直接邊的權重（沒有邊就是 $\infty$，$d[i][i]=0$）。
答案：$d^{(V)}[i][j]$。

func FloydWarshall(d [][]int, n int) {
    // d[i][j] 已初始化為邊權，無邊為 INF，d[i][i] = 0
    for k := 0; k < n; k++ {          // ★ k 必須在最外層
        for i := 0; i < n; i++ {
            if d[i][k] == INF { continue }        // 小優化，也避免溢位
            for j := 0; j < n; j++ {
                if d[k][j] == INF { continue }
                if nd := d[i][k] + d[k][j]; nd < d[i][j] {
                    d[i][j] = nd
                }
            }
        }
    }
}

★ 為什麼 k 必須在最外層（這題唯一的考點）

k 是 DP 的「階段」，i、j 只是這一層要填的表格座標。

第 $k$ 層要用的是第 $k-1$ 層的完整結果。
k 放最外層，表示「在開始第 $k$ 層之前，第 $k-1$ 層的整張表已經全部算完」。

如果把 k 放到內層（例如 for i { for j { for k ），
你會在同一個 i 的表格還沒填完的時候就拿它去算別的格子——
用到的是「半成品」的狀態，結果會少算很多路徑。

★ 而且原地更新（只用一個二維陣列）是安全的：
第 $k$ 層用到的 $d[i][k]$ 和 $d[k][j]$，在第 $k$ 層中不會被改變
（因為 $d^{(k)}[i][k]=d^{(k-1)}[i][k]$——經過 $k$ 再到 $k$ 沒有意義）。
所以不需要開第二個陣列。

⚠️ 順序寫錯的症狀：某些點對的距離偏大，但程式正常結束、沒有任何錯誤訊息。
這是典型的「安靜的錯」——所以要記住 k 在最外層。

複雜度

時間	$\Theta (V^3)$（無論邊多少）
空間	$\Theta (V^2)$

$V$ 的實際上限：

$V$	$V^3$	可行性
100	$10^6$	瞬間
500	$1.25\times 10^8$	可接受（約數百毫秒）
1,000	$10^9$	勉強（數秒），記憶體 8 MB
5,000	$1.25\times 10^{11}$	❌ 不可行；記憶體也要 200 MB

★ $V^2$ 的記憶體常常比 $V^3$ 的時間更早成為瓶頸。

和其他做法的選擇

情況	用什麼
$V$ 小（≤ 500）、要全對	★ Floyd-Warshall —— 程式碼最短、常數極小、快取友善（連續二維陣列）
稀疏大圖、要全對、無負權	跑 $V$ 次 Dijkstra 最短路徑：$O(VE\log V)$
稀疏大圖、有負權	Johnson：一次 Bellman-Ford 最短路徑 做重新賦權消掉負權，再跑 $V$ 次 Dijkstra
只要單源	Dijkstra 或 Bellman-Ford

★ 三個好用的變體（同一個框架換個運算）

變體	把 min(+) 換成	得到什麼
傳遞閉包	or(and) → d[i][j] |= d[i][k] && d[k][j]	i 到不到得了 j（Warshall 演算法）。可改用 bitset 加速到 $O(V^3/64)$
最小瓶頸路	min(max) → d[i][j] = min(d[i][j], max(d[i][k], d[k][j]))	路徑上最大邊權的最小值（瓶頸頻寬、最低承載）
最大可靠度	max(×)	路徑上機率乘積的最大值

★ 這是一個很漂亮的抽象：把 $(\min ,+)$ 換成任何滿足「半環」性質的運算對，演算法就照樣成立。

負權與負環

• 允許負權邊 ✅
• 偵測負環：跑完後檢查 d[i][i] < 0 —— 有任何一個對角線變成負數就代表 $i$ 在某個負環上
• 有負環時其他格子的值無意義

路徑還原

另開 next[i][j] 記錄「從 i 往 j 走的第一步」，在更新時 next[i][j] = next[i][k]，之後逐步跳即可還原完整路徑。

🧪 我實際套用的紀錄

• （待填）

⚠️ 注意 / 什麼時候不適用

• ★ k 一定要在最外層。寫錯不會報錯，只會安靜地算出偏大的距離。
• $V>1000$ 基本不可行（時間 $10^9$、記憶體 $V^2$）。
• INF 要用 math.MaxInt/2 或做檢查，否則 INF + INF 溢位變負數，會產生荒謬的「捷徑」。
• 不要為了「只要幾對」而跑全對。只要少數幾個源點就跑幾次 Dijkstra。
• 稀疏圖上非常浪費：$E\ll V^2$ 時，Floyd 仍然要跑 $V^3$，而 $V$ 次 Dijkstra 只要 $O(VE\log V)$。
• 初始化容易出錯：對角線要設 0、重邊要取最小、有向與無向的初始化不同。
• 快取友善是它的隱藏優勢：連續的二維陣列 + 規律的存取模式，實測常數比理論分析看起來好得多——所以 $V=500$ 時它往往比「跑 500 次 Dijkstra」更快。

🔗 相關工具

• Dijkstra 最短路徑 —— 稀疏圖上跑 V 次的替代方案
• Bellman-Ford 最短路徑 —— Johnson 演算法的前置步驟
• 動態規劃 —— 這是一個教科書級的 DP（階段 = 允許的中繼點集合）
• 演算法導論