Floyd-Warshall 演算法教學：原理、程式碼與時間複雜度

Floyd-Warshall 解決什麼問題

有時你需要的是所有地點兩兩之間的距離，而不只是從單一起點出發：所有城市之間的行車時間表、每對伺服器之間的延遲，或相依關係圖的完整可達性。Floyd-Warshall 用一段非常短的動態規劃演算法解決了這個所有節點對最短路徑問題。

它由 Robert Floyd 於 1962 年發表（「Algorithm 97: Shortest path」），並建立在 Stephen Warshall 同年提出的遞移閉包演算法之上。

用白話說明原理

將節點編號為 0 到 V − 1。處理完節點 k 之後，dist[i][j] 就是只允許使用節點 0 到 k 作為中繼點時，從 i 到 j 的最短路徑。多允許一個中繼節點 k 時有兩種選擇：不經過 k 的舊最佳路徑，或由兩段只使用 k 之前節點的最佳路徑組成的 i → k → j。

1. 填入矩陣：對角線為 0，有邊的位置填入邊權重，其餘填無限大。
2. 對 k = 0 到 V − 1，針對每一對 (i, j)：如果 dist[i][k] + dist[k][j] < dist[i][j]，就更新它。
3. 最後一個 k 處理完後，矩陣就包含所有最短距離。對角線上出現負值，代表存在負環。

迴圈的順序至關重要：k 必須是最外層迴圈。

逐步範例

有向圖有 4 個節點，邊為 0→1（3）、0→3（7）、1→0（8）、1→2（2）、2→0（5）、2→3（1）、3→0（2）。初始矩陣如下（列 = 起點，欄 = 終點）：

1. k = 0：路徑可以經過節點 0。1→3 變成 8 + 7 = 15，2→1 變成 5 + 3 = 8，3→1 變成 2 + 3 = 5。
2. k = 1：經過節點 1。0→2 變成 3 + 2 = 5，3→2 變成 5 + 2 = 7。
3. k = 2：經過節點 2。0→3 從 7 改善為 5 + 1 = 6，1→3 從 15 改善為 2 + 1 = 3，1→0 從 8 改善為 2 + 5 = 7。
4. k = 3：經過節點 3。1→0 從 7 改善為 3 + 2 = 5，2→0 從 5 改善為 1 + 2 = 3，2→1 從 8 改善為 1 + 5 = 6。

最終矩陣各列：0 → [0, 3, 5, 6]，1 → [5, 0, 2, 3]，2 → [3, 6, 0, 1]，3 → [2, 5, 7, 0]。

Python 實作

INF = float("inf")
def floyd_warshall(n, edges):
    dist = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    nxt = [[j if i == j else None for j in range(n)] for i in range(n)]
    for u, v, w in edges:
        dist[u][v] = w
        nxt[u][v] = v
    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]
                    nxt[i][j] = nxt[i][k]
    return dist, nxt
edges = [(0, 1, 3), (0, 3, 7), (1, 0, 8), (1, 2, 2),
         (2, 0, 5), (2, 3, 1), (3, 0, 2)]
dist, nxt = floyd_warshall(4, edges)
for row in dist:
    print(row)
# [0, 3, 5, 6]
# [5, 0, 2, 3]
# [3, 6, 0, 1]
# [2, 5, 7, 0]

nxt 矩陣儲存 i 到 j 最佳路徑上的第一步，這就足以重建任何一條路徑：

def path(nxt, i, j):
    if nxt[i][j] is None:
        return []                         # no path
    route = [i]
    while i != j:
        i = nxt[i][j]
        route.append(i)
    return route
print(path(nxt, 1, 0))  # [1, 2, 3, 0]

如果節點很多、又想在 Python 中提升速度，同樣的三層迴圈可以用 NumPy 寫成每個 k 只做一次向量化更新：d = np.minimum(d, d[:, k, None] + d[None, k, :])。

時間與空間複雜度

對於權重非負的稀疏圖，從每個節點各執行一次 Dijkstra 的成本是 O(V × (V + E) log V)，當 E 遠小於 V² 時，比 O(V³) 更快。

變化版本與常見錯誤

• 負環：迴圈結束後，如果某個 i 的 dist[i][i] < 0，就表示節點 i 位於負環上，經過它的最短路徑沒有定義。
• 遞移閉包（Warshall）：改用布林值，並把 min/加法換成 or/and：reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])。
• 最小最大與最大最小路徑：把 + 換成 max（或 min），例如找出最大邊盡可能小的路徑。
• 只有在確定兩個「無限大」相加不會溢位時，才用很大的有限數字代替無限大；在 Python 中，float("inf") 是安全的選擇。
• 對角線要初始化為 0；有平行邊時只保留最小的權重。

何時使用與實際應用

• 預先計算所有車站、倉庫或城市之間的距離表，供之後查詢。
• 圖分析，例如小型網路的接近中心性或直徑。
• 面試題目：找出在距離門檻內鄰居數量最少的城市、除法求值（比率視為路徑乘積）、把課程先修關係當作遞移閉包。