Floyd-Warshall：算所有點對的最短路

想算所有點對的最短路

之前的 Dijkstra / Bellman-Ford 都是「從一個起點」算最短路。但有時你要的是：任兩個城市之間的最短距離——10×10 城市網路，問 100 個答案。

最笨方法：對每個起點跑 Dijkstra → V 次 → O(V² log V + V × E)。 Floyd-Warshall 用三層 for 一次算完，O(V³)，密集圖時更快、code 還超短。

核心想法：允許用中繼點

定義 dp[k][i][j] = 只允許用編號 1~k 當中繼點時，i 到 j 的最短距離。

每次新增允許 k 當中繼：

dp[k][i][j] = min(
  dp[k-1][i][j],                     # 不走 k
  dp[k-1][i][k] + dp[k-1][k][j]      # 走 k
)

直接把 k 那一維壓掉——只用一個二維 dist 陣列就夠了：

for k from 1 to V:
  for i from 1 to V:
    for j from 1 to V:
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

跑一遍

4 個城市 A, B, C, D。邊：A→B(3), B→C(2), A→C(8), C→D(1), B→D(5)。

初始 dist 矩陣（∞ 表示沒有直接邊）：

	A	B	C	D
A	0	3	8	∞
B	∞	0	2	5
C	∞	∞	0	1
D	∞	∞	∞	0

k = A（允許用 A 當中繼）：A 是起點，沒人能從別處走到 A → 沒變化。

k = B（允許用 B 當中繼）：

dist[A][C] = min(8, dist[A][B]+dist[B][C]) = min(8, 3+2) = 5 ✨
dist[A][D] = min(∞, 3+5) = 8

k = C（允許用 C 當中繼）：

dist[A][D] = min(8, dist[A][C]+dist[C][D]) = min(8, 5+1) = 6 ✨
dist[B][D] = min(5, 2+1) = 3 ✨

k = D：D 沒有出邊 → 沒變化。

最終 dist：

	A	B	C	D
A	0	3	5	6
B	∞	0	2	3
C	∞	∞	0	1
D	∞	∞	∞	0

Pseudocode

Algorithm FloydWarshall(graph):

dist[i][j] ← edge(i, j) if exists else ∞

dist[i][i] ← 0

for k ← 1 to V:

for i ← 1 to V:

for j ← 1 to V:

if dist[i][k] + dist[k][j] < dist[i][j]:

dist[i][j] ← dist[i][k] + dist[k][j]

return dist

5 行核心邏輯，這就是 Floyd-Warshall。

⚠️k 一定要在最外層！

順序是 k → i → j，不是 i → j → k。

如果 k 不在最外層，DP 的依賴會錯——你需要「先算完允許 k 當中繼的所有情況」，再開放 k+1。考試會故意問這個，注意。

複雜度

	Big-O
時間	O(V³)
空間	O(V²)
負邊	✓ 支援
負環	✓ 跑完看 `dist[i][i] < 0` 即可偵測

三大最短路演算法 vs

算法	場景	時間
Dijkstra	單源、非負邊	O((V+E) log V)
Bellman-Ford	單源、可負邊	O(V × E)
Floyd-Warshall	全點對、可負邊	O(V³)

V = 500 時：

500 次 Dijkstra ≈ 500 × 5000 × 10 = 25M
Floyd-Warshall = 500³ = 125M

V = 5000 時：

5000 次 Dijkstra ≈ 5000 × 50000 × 13 = 3 × 10⁹（如果圖密集）
Floyd-Warshall = 1.25 × 10¹¹（跑不完）

Floyd-Warshall 適合小而密集的圖（V ≤ 500）。

📝考試會這樣考

題型一：跑一遍 Floyd-Warshall。 給 3~5 個節點的圖，逐 k 列出 dist 矩陣的變化。訣竅：畫表格，每個 k 一張矩陣。

題型二：為什麼 k 要在最外層？ 答：因為 DP 的狀態是「允許用 {1..k} 當中繼」。要先確定 dp[k-1][i][j]、dp[k-1][i][k]、dp[k-1][k][j] 都已收斂，才能更新 dp[k][i][j]。

題型三：和「跑 V 次 Dijkstra」比，何時用 Floyd-Warshall？ 答：

V 小（≤ 500）：Floyd-Warshall 常數小、code 簡單 → 用它
V 大且邊稀疏：V 次 Dijkstra 較快
有負邊：Bellman-Ford 或 Floyd-Warshall

題型四：怎麼偵測負環？ 答：跑完後檢查 dist[i][i] < 0——如果某個節點到自己的距離變成負數，代表存在通過它的負環。

題型五：能不能用 Floyd-Warshall 找最短「路徑」（不只距離）？ 答：可以，加一個 next[i][j] 陣列記錄「i 到 j 的第一步該走哪」，更新時同步寫入 next[i][j] = next[i][k]。

這章記住

三層 for，k 必須在最外層。
時間 O(V³)，空間 O(V²)，負邊可、負環可偵測。
適合 V 小但要算全部點對最短距離 的場景。
Code 短到能默寫——這是它的最大魅力。