Floyd-Warshall：圖論中的上帝視角

演算法背後的故事：「中間人」的力量

1962 年，電腦科學界正在熱議一個問題：「傳遞閉包 (Transitive Closure)」。這個聽起來很學術的名詞，其實描述了一個簡單的社交概念：如果 Alice 認識 Bob，而 Bob 認識 Charlie，那麼 Alice 實際上也就認識了 Charlie。

Robert Floyd 和 Stephen Warshall 幾乎在同一時間獨立發表了解決這個問題的演算法。她們意識到，要理解一張圖，並不需要親自在裡面奔波。妳只需要系統性地引入「中間人」。

她們的演算法與眾不同。它沒有起點，也沒有終點。它只是靜靜地注視著整個數據宇宙，然後問一個問題：「如果我讓每個人都充當一次聯絡員，我們能不能看清所有人之間的真正關係？」

為什麼需要它？

Dijkstra 和 A* 是 單源 (Single-Source) 演算法。她們告訴妳如何從 家 到 任何地方。 但有時候，妳需要的是 全源 (All-Pairs) 的知識。

• 網約車調度： 系統需要瞬間知道 每一輛車 到 每一個乘客 的距離。
• 社群網路分析： 要確定誰是社交圈的「中心」，妳需要知道他離 其他人 到底有多近。

執行 N 次 Dijkstra 既麻煩又難寫。Floyd-Warshall 用一種極度優雅的方式，一次性交給妳一張包含所有距離的終極表格。

演算法是如何「思考」的

Floyd-Warshall 可能是圖論中最優雅——也可能是最傲慢——的演算法。它以一種 「上帝模式 (God-Mode)」 進行思考。

1. 佈局： 它首先鋪開一張巨大的表格（矩陣），代表當下的世界。

   • 如果 $i$ 和 $j$ 之間有直接的路，寫下成本。
   • 如果沒有，寫下 $\infty$。
   • 任何人到自己的距離都是 0。

2. 引薦： 然後，它開始了一場迴圈。它選中一個節點——我們叫它 $k$——並將它作為 「中間人」 介紹給全世界。 它會問每一對節點 ($i$ 和 $j$) 一個問題：

   「嘿 $i$，妳現在是直接去 $j$（或者根本到不了）。但如果妳經由 $k$ 中轉一下 ($i \to k \to j$)，會不會更快？」

   如果答案是肯定的，世界地圖就會瞬間更新。舊的路被遺忘，經由中間人的新路成為了標準。

3. 共識： 它會對圖中的每一個節點重複這個過程。首先是節點 A 當中間人，然後是 B，然後是 C…… 當最後一個節點也完成中間人的使命時，矩陣中留下的，就是任意兩點間確鑿無疑的最短路徑。

「鬆弛」的邏輯

這種「檢查第三方能否改善關係」的邏輯，正是 動態規劃 (Dynamic Programming) 的核心。它自底向上地建構解決方案，確保在結束時，沒有任何更短的路徑被遺漏，因為每一種組合都被測試過了。

工程決策：全知全能的代價

Floyd-Warshall 的代碼短得驚人——核心邏輯只有四行。但這種優雅伴隨著沉重的代價：$O(V^3)$ 的複雜度。

• 對於 100 個節點，它做約 100 萬次運算。（瞬間完成）
• 對於 1,000 個節點，它做約 10 億次運算。（很慢）
• 對於 10,000 個節點，它做約 1 萬億次運算。（算不完）

什麼時候用它？

• 小型稠密圖： 當節點少於 500 個，但連線非常密集時（比如管理主要機場之間的航線）。
• 預計算 (Pre-computation)： 當地圖很少變化時，妳願意支付一次昂貴的計算成本，以換取未來每一次查詢都是 $O(1)$ 的極致速度。

實作參考 (Python)

這可能是妳寫過的最短的路徑演算法代碼。

def floyd_warshall(graph_matrix):
    """
    graph_matrix: 二維列表 (V x V)，graph_matrix[i][j] 是權重。
    不相連則用 float('inf') 表示。
    """
    V = len(graph_matrix)
    
    # 我們創建一個副本，避免直接修改輸入數據
    dist = [row[:] for row in graph_matrix]

    # 核心：三個巢狀迴圈
    # k = 中間人
    # i = 起點
    # j = 終點
    for k in range(V):
        for i in range(V):
            for j in range(V):
                
                # 黃金問題：
                # 經由 k 中轉，是否比當前已知的路 (i->j) 更快？
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

# 使用範例
# inf = float('inf')
# graph = [
#     [0,   5,   inf, 10],
#     [inf, 0,   3,   inf],
#     [inf, inf, 0,   1],
#     [inf, inf, inf, 0]
# ]
# print(floyd_warshall(graph))

小結

Floyd-Warshall 教會了我們視角的價值。它不急於從 A 奔向 B，而是透過系統性地建立共識，一遍又一遍地詢問：「如果我們要經過中間人協作，能不能做得更好？」 它很慢，但它極其徹底——最終，它知曉一切。