在前兩天我們分別介紹了 Dijkstra 與 Bellman-Ford ，它們都解決的是 單源最短路徑 (Single Source Shortest Path, SSSP) 問題。今天要介紹的是 Floyd-Warshall 演算法 —— 一個能計算 所有點對 (All-Pairs Shortest Path, APSP) 的演算法

演算法背景

• 適用情境
  • 計算圖中 任意兩點之間的最短路徑
  • 圖可以包含 負權重邊，但 不能有負權重環
• 典型應用: 交通網路、路由系統、關係強度分析

核心思想

Floyd-Warshall 採用 動態規劃 (Dynamic Programming, DP) 的方式，逐步引入節點作為「中繼點」，不斷更新最短路徑

定義狀態:

• $dist[i][j]$ = 節點 $i$ 到節點 $j$ 的最短距離

轉移方程:

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

意思是: 如果從 $i$ 經過 $k$ 再到 $j$ 的路徑更短，就更新 $dist[i][j]$

演算法流程

• 初始化距離矩陣
  • 若有邊 $(i, j)$，則 dist[i][j] = w(i,j)
  • 若沒有邊，則設為無限大
  • dist[i][i] = 0
• 對每個節點 $k$，嘗試更新所有 $(i, j)$ 的最短路徑
• 重複 $V$ 次 ($V$ 為節點數)

程式碼範例

INF = float('inf')

def floyd_warshall(graph):
    # graph: adjacency matrix 格式
    V = len(graph)
    dist = [row[:] for row in graph]  # 複製矩陣

    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist


# 測試
graph = [
    [0,   3,   INF, 7],
    [8,   0,   2,   INF],
    [5,   INF, 0,   1],
    [2,   INF, INF, 0]
]

result = floyd_warshall(graph)
for row in result:
    print(row)

複雜度分析

• 時間複雜度: $O(V^3)$
• 空間複雜度: $O(V^2)$

相較於 Dijkstra 與 Bellman-Ford，Floyd-Warshall 適合 節點數不多 (n ≤ 400~500) 的情境，因為它會遍歷所有三元組 $(i, j, k)$

優缺點

應用場景

• 交通路網分析
  • 任意兩城市之間的最短距離
  • 可用於航線、地鐵系統的最優化設計
• 網路路由 (All-Pairs Routing)
  • 適用於節點較少但需要完整路由表的小型網路
• 社交網路分析
  • 分析兩個使用者之間的最短連結 (最少跳數或最短影響力)

結語

Floyd-Warshall 演算法雖然比不上 Dijkstra 與 Bellman-Ford 的效率，但它在小規模圖的全點對最短路徑問題中極具威力，它的動態規劃思想也為理解更複雜的演算法奠定基礎。