Floyd-Warshall全點對最短路徑

01為什麼需要它

看到這些關鍵字就想到它：任意兩點之間的最短距離都要、節點數在幾百以內、圖很稠密、有負權邊但沒有負環、可達性或遞移閉包、瓶頸路徑、需要大量兩點查詢。

02核心概念

全點對最短路徑要算出每一對 (i, j) 的最短距離。可以從每個點各跑一次 Dijkstra，但遇到負權邊就不行；每個點各跑一次 Bellman-Ford 則是 O(V²E)。Floyd-Warshall 用動態規劃一次解決，程式只有三層迴圈。狀態定義為：d_k[i][j] 是從 i 到 j、中間只允許經過前 k 個節點的最短距離。k = 0 時不能經過任何中間點，就是原始的邊；允許經過全部 V 個節點時，就是真正的答案。

從 d_(k−1) 推到 d_k 只要考慮新加入的節點 k。最短路徑要嘛沒經過 k，距離仍是 d_(k−1)[i][j]；要嘛經過 k，而沒有負環時最短路徑不會重複經過同一個點，所以恰好經過一次，拆成 i 到 k、k 到 j 兩段，每段的中間點都只用到前 k − 1 個：d_k[i][j] = min(d_(k−1)[i][j], d_(k−1)[i][k] + d_(k−1)[k][j])。k 必須放在最外層。三維的表可以壓成一張二維矩陣原地更新，因為第 k 輪裡第 k 列和第 k 行不會改變：d[i][k] + d[k][k] 裡的 d[k][k] = 0。

時間 O(V³)，空間 O(V²)。V = 500 大約是 1.25 億次簡單運算，C++ 不到一秒；V 到幾千就太慢了，稀疏且沒有負權的圖改用每個點跑一次 Dijkstra 的 O(V·E log V)。算完之後若有某個 d[i][i] < 0，表示從 i 出發能繞回自己而且總權重是負的，也就是負環。要還原路徑就多存一張 next[i][j]，表示從 i 往 j 的第一步，更新時令 next[i][j] = next[i][k]。把加法和取最小換成其他運算，同一個骨架還能算遞移閉包（AND、OR）和最大瓶頸路徑（min、max）。

常見的坑：把 k 放在內層迴圈，得到的不是最短距離；用 INT_MAX 當無限大，兩個相加就溢位，或是 ∞ 加上負權以後看起來比 ∞ 小，產生其實走不到的假路徑，所以兩段都要先確認不是 ∞；忘了把 d[i][i] 設為 0；同一對節點有多條邊時沒有取最小；無向圖只設了一個方向。有負環時矩陣的值沒有意義，而且數字會越來越小，嚴重時也會溢位。和鄰近課程的關係：Dijkstra 和 Bellman-Ford 是單源，Floyd-Warshall 是全點對；它用的是 Adjacency Matrix 表示法；狀態「只允許前 k 個中間點」是很典型的 DP 設計。

03演算法步驟

1. 1建 V × V 的矩陣 dist：dist[i][i] = 0，每條邊 u → v 設為 min(原值, w)，其餘為 ∞；要還原路徑就同時令 next[u][v] = v。
2. 2最外層 k 從 0 到 V − 1，代表「現在允許經過 k」。
3. 3內兩層枚舉 i、j：若 dist[i][k] 和 dist[k][j] 都不是 ∞，而且兩者相加小於 dist[i][j]，就更新 dist[i][j]，並令 next[i][j] = next[i][k]。
4. 4三層迴圈結束後檢查對角線，任何 dist[i][i] < 0 都表示圖中有負環。
5. 5查詢距離直接讀 dist[i][j]；要路徑就從 i 出發，反覆走到 next[目前][j]，直到抵達 j。

04互動示範

4 個節點、8 條有向邊，B → C 的權重是 −2。右邊的距離矩陣一開始只有直接相連的邊。每一輪先選定中間點 k（黃色節點，矩陣裡第 k 列和第 k 行加上黃框），接著逐一顯示這一輪有被改小的格子：藍色是正在更新的 dist[i][j]，實心黃色是它用到的 dist[i][k] 和 dist[k][j]，綠色是這一輪已經更新過的格子。k = A 讓 C、D 能經過 A 走到 B；k = B 把負權邊用上，A → C 從 ∞ 變成 2、D → C 從 8 變成 3；k = C 和 k = D 再各改 3 格，其中 B → A 和 C → B 都被改了兩次。最後檢查對角線沒有負數，並用 next 表還原 D 到 C 的最短路徑 D → A → B → C，總長 3。

05程式碼

Python 放完整版：處理重複邊、記錄 next 還原路徑、檢查負環，另外附上用位元集合做遞移閉包的 Warshall 版本，以角色繼承為例。C++ 放原地更新的最短距離版本，INF 取最大值的四分之一以免相加溢位，並示範把運算換成 min 和 max 的最大頻寬路徑。

INF = float("inf")


def floyd_warshall(n, edges):
    """回傳 (dist, nxt)：dist[i][j] 是 i 到 j 的最短距離，nxt[i][j] 是路徑上 i 之後的第一個節點。O(V³)"""
    dist = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    nxt = [[i if i == j else None for j in range(n)] for i in range(n)]
    for u, v, w in edges:
        if w < dist[u][v]:                      # 同一對節點有多條邊時取最小
            dist[u][v] = w
            nxt[u][v] = v
    for k in range(n):                          # k 一定要在最外層
        for i in range(n):
            if dist[i][k] == INF:
                continue
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]       # 先往 k 的方向走
    return dist, nxt


def has_negative_cycle(dist):
    return any(dist[i][i] < 0 for i in range(len(dist)))


def get_path(nxt, u, v):
    if nxt[u][v] is None:                       # 走不到
        return []
    path = [u]
    while u != v:
        u = nxt[u][v]
        path.append(u)
    return path


def transitive_closure(n, edges):
    """Warshall：reach[i] 的第 j 個位元表示 i 能不能走到 j。用整數當位元集合，一次 OR 一整列"""
    reach = [1 << i for i in range(n)]
    for u, v in edges:
        reach[u] |= 1 << v
    for k in range(n):
        for i in range(n):
            if reach[i] >> k & 1:               # i 走得到 k，k 走得到的 i 也都走得到
                reach[i] |= reach[k]
    return reach


if __name__ == "__main__":
    A, B, C, D = range(4)
    edges = [(A, B, 4), (A, D, 9), (D, A, 1), (B, C, -2), (B, D, 5), (C, D, 3), (D, C, 8), (C, A, 6)]
    dist, nxt = floyd_warshall(4, edges)
    for row in dist:
        print(row)                              # [0, 4, 2, 5] / [2, 0, -2, 1] / [4, 8, 0, 3] / [1, 5, 3, 0]
    print("".join("ABCD"[x] for x in get_path(nxt, D, C)))   # DABC
    bad = [(u, v, -9 if (u, v) == (B, C) else w) for u, v, w in edges]
    print(has_negative_cycle(floyd_warshall(4, bad)[0]))      # True：B → C → D → A → B 總和 -1

    roles = ["admin", "editor", "viewer", "auditor"]
    reach = transitive_closure(4, [(0, 1), (1, 2), (3, 2)])  # admin 繼承 editor，editor 繼承 viewer
    print([roles[j] for j in range(4) if reach[0] >> j & 1])  # ['admin', 'editor', 'viewer']

06練習題

• LeetCode 1334Find the City With the Smallest Number of Neighbors at a Threshold DistanceMedium
• LeetCode 1462Course Schedule IV（遞移閉包）Medium
• LeetCode 399Evaluate Division（把加法換成乘法的 Floyd-Warshall）Medium
• LeetCode 2976Minimum Cost to Convert String I（26 個字母之間的最短轉換成本）Medium
• LeetCode 2959Number of Possible Sets of Closing Branches（枚舉子集合，每次跑一次 Floyd-Warshall）Hard
• LeetCode 2977Minimum Cost to Convert String IIHard