跳至主要内容

Floyd-Warshall's Algorithm

預備知識

Floyd-Warshall's Algorithm 是用來計算 Graph 中 「所有點對所有點」的最短路徑（All-Pairs Shortest Path） 的演算法。

和 Dijkstra's Algorithm 只解決「一個起點到其他所有點」的最短路徑不同，Floyd-Warshall 一次就能算出「任兩點之間」的最短距離。

白話理解

想像一張城市地圖，你想知道「任何一座城市」到「任何另一座城市」最快要多久。做法是：一個一個把城市當作「轉運站」開放，每開放一座城市，就重新檢查所有城市對，看看「繞道經過這座城市」會不會比原本記錄的路徑更短。全部城市都當過一次轉運站後，答案就完全確定了。

核心概念：動態規劃​

Floyd-Warshall 本質上是一種 Dynamic Programming。它用一個 dist[i][j] 的表格記錄「i 到 j 目前已知的最短距離」，並且反覆問自己同一個問題：

「如果允許繞道經過節點 k，i 到 j 的距離會不會變得更短？」

用公式表示就是：

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

只要把 k 從第一個節點依序試到最後一個節點，並且對「每一對」i 和 j 都做這個檢查，最終 dist[i][j] 就會是 i 到 j 真正的最短距離。

實作​

def floyd_warshall(graph):
    # graph 是一個 n x n 的鄰接矩陣
    # graph[i][j] 代表 i 到 j 的直接距離，沒有邊則為 float('inf')，i 到自己為 0
    n = len(graph)
    dist = [row[:] for row in graph]  # 複製一份，避免修改到原始資料

    # k 一定要放在最外層迴圈！代表「依序開放每一個轉運站」
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]  # 繞道經過 k 反而更短，更新紀錄

    return dist
三層迴圈的順序不能亂放

k（轉運站）一定要放在最外層。因為每一輪都必須確保「前一個轉運站帶來的優化」已經完全套用到整張表上，才能開放下一個轉運站，如果把 i 或 j 放在最外層，會漏掉某些應該被更新的路徑組合。

逐步拆解：以 4 個城市為例​

假設城市 A(0)、B(1)、C(2)、D(3)，初始的直接距離（鄰接矩陣，∞ 代表沒有直接道路）：

       A    B    C    D
  A  [  0,   3,   ∞,   7 ]
  B  [  8,   0,   2,   ∞ ]
  C  [  5,   ∞,   0,   1 ]
  D  [  2,   ∞,   ∞,   0 ]

開放 A（k=0）當轉運站：檢查所有 dist[i][A] + dist[A][j] 是否比 dist[i][j] 更短，例如 dist[D][B] 原本是 ∞，但 dist[D][A] + dist[A][B] = 2 + 3 = 5 更短，更新成 5。全部檢查完後：

       A    B    C    D
  A  [  0,   3,   ∞,   7 ]
  B  [  8,   0,   2,  15 ]   ← B→A→D = 8+7 = 15
  C  [  5,   8,   0,   1 ]   ← C→A→B = 5+3 = 8
  D  [  2,   5,   ∞,   0 ]   ← D→A→B = 2+3 = 5

開放 B（k=1）當轉運站：檢查所有 dist[i][B] + dist[B][j]，例如 dist[A][C] 原本 ∞，透過 A→B→C = 3+2 = 5 更短：

       A    B    C    D
  A  [  0,   3,   5,   7 ]   ← A→B→C = 3+2 = 5
  B  [  8,   0,   2,  15 ]
  C  [  5,   8,   0,   1 ]
  D  [  2,   5,   7,   0 ]   ← D→B→C = 5+2 = 7

開放 C（k=2）當轉運站：檢查所有 dist[i][C] + dist[C][j]，這一輪有好幾個組合都被縮短：

       A    B    C    D
  A  [  0,   3,   5,   6 ]   ← A→C→D = 5+1 = 6（比原本的 7 更短）
  B  [  7,   0,   2,   3 ]   ← B→C→A = 2+5 = 7；B→C→D = 2+1 = 3
  C  [  5,   8,   0,   1 ]
  D  [  2,   5,   7,   0 ]

開放 D（k=3）當轉運站：檢查所有 dist[i][D] + dist[D][j]：

       A    B    C    D
  A  [  0,   3,   5,   6 ]
  B  [  5,   0,   2,   3 ]   ← B→D→A = 3+2 = 5（比剛才的 7 更短）
  C  [  3,   6,   0,   1 ]   ← C→D→A = 1+2 = 3；C→D→A→B = 1+2+3 = 6
  D  [  2,   5,   7,   0 ]

四個轉運站都開放完畢，這張表就是任兩個城市之間真正的最短距離。例如最終 dist[C][B] = 6，實際走的路線是 C → D → A → B（1 + 2 + 3 = 6），比原本「C 到 B 沒有直接道路」進步非常多，而且這個過程完全不需要針對每一對城市各自跑一次搜尋，一次計算就能得到所有答案。

複雜度​

項目複雜度說明
時間複雜度O(V^3)三層迴圈，每層都跑過所有節點
空間複雜度O(V^2)需要一張 V × V 的表格記錄所有點對的距離

Floyd-Warshall vs Dijkstra​

比較項目Floyd-WarshallDijkstra
解決的問題所有點對所有點的最短路徑一個起點到其他所有點的最短路徑
時間複雜度O(V^3)O((V + E) log V)（使用 Min-Heap）
能否處理負權重可以（但不能有「負權重環」）不行，只要有負權重就可能出錯
適合場景節點數量不多、需要頻繁查詢「任兩點」距離節點數量大、只在乎「單一起點」出發的最短距離
新手小提醒

如果只需要「一個起點」到其他點的最短路徑，直接用 Dijkstra 就好，時間複雜度更低；只有當你需要「任意兩點」的最短距離，或是圖中可能存在負權重（但沒有負環）時，才需要動用 Floyd-Warshall。

適用情況​

  • 節點數量不多、需要頻繁查詢任兩點距離：例如城市間的距離表，一次計算好之後，之後任何兩座城市之間的查詢都是 O(1)。
  • 圖中可能存在負權重（但沒有負權重環）：Dijkstra 無法處理負權重，這種情況需要改用 Floyd-Warshall。
  • 需要判斷圖中是否存在負權重環：如果計算完成後發現某個 dist[i][i] 變成負數，代表圖中存在負權重環（Bellman-Ford 與 SPFA 也都能偵測負權重環，但那兩個是針對「單一起點」，Floyd-Warshall 則是一次判斷整張圖）。
  • 小規模的路網規劃：例如遊戲地圖中少量據點之間互相計算最短距離。

常見誤區​

  • 三層迴圈順序寫錯：k 沒有放在最外層，會導致某些應該被更新的路徑漏掉，得到錯誤答案，務必牢記「先決定轉運站，再檢查所有點對」。
  • 忘記初始化對角線與無邊的情況：dist[i][i] 應該初始化為 0（自己到自己不用移動），沒有直接道路的 dist[i][j] 應該設為 Infinity，這兩個初始值設錯，後續計算全部都會跟著錯。
  • 忽略「負權重環（Negative Cycle）」：如果圖中存在一個總權重為負的環，代表可以無限繞圈讓距離持續變小，理論上不存在「最短路徑」，使用前建議先確認圖中沒有負權重環。
  • 誤以為 Floyd-Warshall 在稀疏圖（Sparse Graph）也划算：O(V^3) 在節點數很多時會變得非常慢，如果圖很大、邊很少，且只需要單一起點的最短路徑，用 Dijkstra 對每個起點各跑一次，通常都比 Floyd-Warshall 更快。
最後於 更新