項目	Floyd–Warshall	Johnson
問題類型	全點對最短路	全點對最短路
方法	動態規劃	Bellman–Ford + Dijkstra（重權後跑多次 Dijkstra）
允許負邊	YES（無可達負環）	YES（先以 Bellman–Ford 重權；無可達負環）
允許負環	NO	NO
時間複雜度	$O(V^3)$	$O(V^2\log V + V E)$

All-pairs shortest paths（用「Single Source 法重複跑」）

• 方法概念：把每個頂點當成來源，重複執行單源最短路演算法，蒐集所有 $s\to v$ 的距離與路徑。

• Dijkstra × $n$ 次（不可有負邊）

  • 鄰接矩陣：每次 $O(V^{2)$，共 $n=V$ 次 ⇒ **$O(V}3)$**。

  • 鄰接串列＋最小堆：每次 $O((V+E)\log V)$ ⇒ $O(VE\log V)$（亦可寫 $O(V^2\log V + VE\log V)$）。

  • 優點：稀疏圖快；缺點：不能有負邊。

• Bellman–Ford × $n$ 次（允許負邊，能偵測負環）

  • 鄰接串列：每次 $O(VE)$ ⇒ $O(V^2E)$。

  • 鄰接矩陣：每次 $O(V^{3)$ ⇒ **$O(V}4)$**。

  • 優點：可處理負邊；缺點：時間較長。

• 更合適的全對方案（參考）

  • Floyd–Warshall：$O(V^3)$（動態規劃，允許負邊，無可達負環）。

  • Johnson：先重權後多次 Dijkstra，$O(V^2\log V + VE)$（允許負邊，無可達負環）。

Floyd-Warshall

• 問題：全點對最短路（允許負邊，無可達負環）。

• 狀態定義：令 $A^{k}(i,j)$ 為「從 $i$ 到 $j$ 的最短路成本，且中繼頂點的索引不大於 $k$」。

  • 基底：$A^{0}(i,j)=\text{COST}(i,j)$（鄰接成本矩陣；無邊為 $\infty$，$i=j$ 為 $0$）。

  • 遞迴：
    $$
    A^{k}(i,j)=\min\Big(A^{k-1}(i,j),\ A^{k-1}(i,k)+A^{k-1}(k,j)\Big),\quad k=1,\dots,n.
    $$

• 直觀：考慮是否讓 $k$ 作為最後一個允許的中繼點。要嘛不用 $k$（左項），要嘛走 $i\to k$ 再 $k\to j$（右項）。

• 演算法（$O(V^3)$）

FLOYD_WARSHALL(COST, n) # 是幾個 vertexs
  A ← COST                      # A[i][j] 初始成本
  PI[i][j] ← (i≠j and COST[i][j]<∞) ? i : NIL   # 前驅矩陣

  for k = 1..n:
    for i = 1..n:
      for j = 1..n:
        if A[i][k] + A[k][j] < A[i][j]:
          A[i][j]  = A[i][k] + A[k][j]
          PI[i][j] = PI[k][j]  # 走經 k 時，j 的前驅沿用「k→j」那段的前驅

  # 負環檢測：若 A[v][v] < 0 則 v 可達負環
  hasNegCycle = (∃ v : A[v][v] < 0)
  return (A, PI, hasNegCycle)

• 回溯路徑（由 $i$ 到 $j$） 反覆令 $j ← \text{PI}[i][j]$ 直到回到 $i$；若遇 NIL 表示不連通。

• 複雜度：時間 $O(V^{3)$，空間 $O(V}2)$。

• 備忘

  • 若任意 $A^{n}(v,v)<0$，存在可達負環。

  • 需要實際路徑就維護前驅矩陣（如上）。

範例

應用

• 目標

  • $A^{+}$：轉移閉包（長度 $\ge 1$ 的可達性）。

  • $A^{*}$：反身轉移閉包（長度 $\ge 0$，含對角線）。

  • 皆以 Warshall 布林版 計算，時間 $O(V^{3})$、空間 $O(V^{2})$。

• 定義

  • 給定鄰接矩陣（布林）$C[1..n,1..n]$，$C[i,j]=1$ 表示有邊 $i\to j$。

  • $A^{+}[i,j]=1 \iff$ 存在長度 $\ge 1$ 的路徑 $i\leadsto j$。

  • $A^{_}[i,j]=1 \iff$ 存在長度 $\ge 0$ 的路徑（含 $i=j$）。等價 $A^{_}=A^{+}\lor I$。

• 演算法（布林運算）

  $A^+$（遞移閉包）

  Aplus(C, n):
    A ← C                          # 初始：只知道一跳可達
    for k = 1..n:                  # 允許的中繼點逐步擴張
      for i = 1..n:
        for j = 1..n:
          A[i][j] = A[i][j] or (A[i][k] and A[k][j])
    return A                        # 即 A^+
  

  __$A^*$（反身遞移閉包）

  Astar(C, n):
    A ← C
    for i = 1..n: A[i][i] = 1       # 先補上長度 0 自迴路
    for k = 1..n:
      for i = 1..n:
        for j = 1..n:
          A[i][j] = A[i][j] or (A[i][k] and A[k][j])
    return A                        # 即 A^*
  

• 關係與實務

  • 已得 $A^{_}$ 時，$A^{+}$ 可直接由 $A^{_}$ 將對角線清為 0 得到。

  • 利用 $A^{_}$ 可判斷強連通（$A^{_}[i,j]=A^{*}[j,i]=1$）、回答任意可達性查詢（$O(1)$）。

Johnson

1. 核心問題

此演算法用於解決「全點對最短路徑 (All-Pairs Shortest Path, APSP)」問題。

• 適用情境：

  1. 圖是稀疏的 (Sparse graph)，即邊的數量 $E$ 遠小於 $V^2$。

  2. 圖中允許有「負權重邊」。

  3. 圖中不允許有「負權重環路 (Negative-weight cycle)」。

• 為什麼需要它？

  • 方法1：跑 $V$ 次 Dijkstra

    • 問題：Dijkstra 演算法無法處理「負權重邊」。

  • 方法2：跑 $V$ 次 Bellman-Ford

    • 問題：可以處理負邊，但時間複雜度 $O(V \cdot VE) = O(V^2E)$，在 $V$ 很大時效率不彰。

Johnson’s 演算法的目標就是結合兩者的優點：只跑一次 Bellman-Ford，然後跑 $V$ 次 Dijkstra，從而提高效率。

2. 核心思想：「重設權重 (Re-weighting)」

Johnson’s 演算法的精髓在於，它不直接在原始圖上操作，而是執行以下步驟：

1. 轉換：建立一個全新的圖 $G’$，其邊權重 $\hat{w}(u, v)$ 全部 $\ge 0$。

2. 保持最短路徑：這個轉換必須保證，原始圖 $G$ 中的「最短路徑」在 $G’$ 中「仍然是」最短路徑。（雖然路徑的總長度值會改變，但「哪一條」路最短是不變的。）

3. 執行 Dijkstra：既然 $G’$ 中所有邊都 $\ge 0$，我們就可以安全地在 $G’$ 上以每個點為源點，執行 $V$ 次 Dijkstra。

4. 還原：最後，將 Dijkstra 算出的新路徑總長 $\hat{\delta}$，「還原」回原始的路徑總長 $\delta$。

3. 演算法步驟

這對應你提供的那張虛擬碼 (pseudocode) JOHNSON(G, w)：

步驟 1：新增超級源點 $s$ (第 1 行)

• 建立一個新圖 $G’$。

• 加入一個新的「超級源點」 $s$。

• 從 $s$ 向原始圖中的每一個節點 $v$，連一條權重為 $0$ 的邊。

• 目的：為 Bellman-Ford 演算法提供一個統一的起始點。

步驟 2：執行 Bellman-Ford (第 2-3 行)

• 以 $s$ 為源點，在 $G’$ 上執行一次 Bellman-Ford。

• 目的 A (檢查負環)：如果 Bellman-Ford 回傳 FALSE，代表它偵測到了「負權重環路」。演算法停止，回報錯誤。

• 目的 B (取得 $h(v)$)：如果回傳 TRUE（沒有負環），演算法會計算出 $s$ 到所有 $v$ 的最短路徑 $\delta(s, v)$。

步驟 3：設定「勢能」 $h(v)$ (第 4-5 行)

• 將 Bellman-Ford 算出的最短路徑 $\delta(s, v)$ 儲存起來，稱之為 $h(v)$。

• $h(v) = \delta(s, v)$

• （因為 $s$ 到所有點的邊權重為 0，且 Bellman-Ford 會處理負邊，所以 $h(v)$ 值可能為 0 或負數）。

步驟 4：重設權重 (Re-weighting) (第 6-7 行)

• 遍歷原始圖中的每一條邊 $(u, v)$。

• 使用以下公式計算新的權重 $\hat{w}(u, v)$：

  $$\hat{w}(u, v) = w(u, v) + h(u) - h(v)$$

• 保證：經過這個轉換，所有 $\hat{w}(u, v)$ 都會 $\ge 0$。

步驟 5：執行 $V$ 次 Dijkstra (第 8-10 行)

• 建立一個 $n \times n$ 的矩陣 $D$ 來存放最終答案（虛擬碼第 8 行）。

• for 迴圈：讓原始圖中的每一個節點 $u$ 依序擔任一次源點。

• 在新權重圖（使用 $\hat{w}$）上，以 $u$ 為源點執行 Dijkstra，計算出 $u$ 到所有其他 $v$ 的最短路徑 $\hat{\delta}(u, v)$。

步驟 6：還原答案 (第 11-12 行)

• Dijkstra 算出的 $\hat{\delta}(u, v)$ 是「新權重」下的路徑長。

• 我們必須用以下公式將它「還原」回「原始權重」下的路徑長 $d_{uv}$：

  $$d_{uv} = \hat{\delta}(u, v) + h(v) - h(u)$$

• 將 $d_{uv}$ 存入答案矩陣 $D[u][v]$。

步驟 7：回傳 (第 13 行)

• 回傳填滿所有最短路徑的矩陣 $D$。

4. 關鍵推導：為什麼 Re-weighting 有效？

1. 定義：

   • 新權重： $\hat{w}(u, v) = w(u, v) + h(u) - h(v)$

   • 一條路徑 $p$： $p = (v_0, v_1, \ldots, v_k)$（從 $v_0$ 到 $v_k$）

2. 推導新路徑總長 $\hat{w}(p)$：

   • $\hat{w}(p) = \sum_{i=1}^{k} \hat{w}(v_{i-1}, v_i)$

   • 代入公式： $\hat{w}(p) = \sum ( w(v_{i-1}, v_i) + h(v_{i-1}) - h(v_i) )$

   • 拆開 $\sum$： $\hat{w}(p) = \sum w(v_{i-1}, v_i) + \sum ( h(v_{i-1}) - h(v_i) )$

3. 分析兩部分：

   • 第一部分：$\sum w(v_{i-1}, v_i)$ 就是原始路徑總長 $w(p)$。

   • 第二部分：$\sum ( h(v_{i-1}) - h(v_i) )$ 是一個「伸縮和 (Telescoping Sum)」

     • 展開 = $(h(v_0) - h(v_1)) + (h(v_1) - h(v_2)) + \ldots + (h(v_{k-1}) - h(v_k))$

     • 中間項 ($-h(v_1)$ 和 $+h(v_1)$ 等) 全部抵銷。

     • 只剩下： $h(v_0) - h(v_k)$ (起點的 $h$ 值 - 終點的 $h$ 值)

4. 結論：

   • $\hat{w}(p) = w(p) + h(v_0) - h(v_k)$

5. 這條公式的意義 (最直觀的部分)：

   • 對於任何一條從 $v_0$ 走到 $v_k$ 的路徑，不管它怎麼繞，它都會被加上同一個常數 ($h(v_0) - h(v_k)$)。

   • 既然所有路徑都被「公平地」平移了相同的值，那麼原始的最短路徑，在新圖中也必然是相對最短的。

5. 複雜度總結

• Step 1 (加 $s$): $O(V)$

• Step 2 (Bellman-Ford): $O(VE)$

• Step 3 (Re-weighting): $O(E)$

• Step 4 ( $V$ 次 Dijkstra): $O(V \times (E + V \log V))$ (使用二元堆積)

• Step 5 (還原): $O(V^2)$

總時間複雜度： $O(VE + V(E + V \log V))$，或寫為 $O(V E + V^2 \log V)$。

• 在稀疏圖 ($E \approx V$) 中，複雜度約為 $O(V^2 \log V)$。

• 這遠優於跑 $V$ 次 Bellman-Ford 的 $O(V^{2E)$ (在稀疏圖中為 $O(V}3)$)。

• 在稠密圖 ($E \approx V^{2$) 中，複雜度為 $O(V}3)$，與 Floyd-Warshall 相同。

範例

1. 圖 (a): 步驟 1 & 2 (新增 $s$ 並執行 Bellman-Ford)

這張圖的左半邊 (a) 顯示了演算法的前兩個步驟：

1. 步驟 1 (Add a new vertex called s)：

   • 如紅色箭頭所指，演算法會先抓取原始圖 $G$（圖中 5 個節點組成的五邊形，注意它有負邊，例如從右邊 $v_3$ 到 $v_4$ 的權重是 -5）。

   • 然後，它會加入一個新的「超級源點」 $s$（圖中的藍色節點，標示為 0）。

   • $s$ 會連一條權重為 0 的邊到所有 5 個原始節點。

   • 這整個「$s$ + 原始圖」就是新圖 $G’$。

2. 步驟 2 (執行 Bellman-Ford)：

   • 演算法會以 $s$ 為源點，在 $G’$ 上執行一次 Bellman-Ford。

   • 執行結果：就是圖 (a) 中，5 個原始節點內部標示的數字！這些就是 $h(v)$ 的值 (即 $\delta(s, v)$)。

     • $h(v_1)$ (top-left) = 0

     • $h(v_2)$ (top-right) = -1

     • $h(v_3)$ (far-right) = -3

     • $h(v_4)$ (bottom-right) = 0

     • $h(v_5)$ (bottom-left) = -4

2. 圖 (b): 步驟 4 (Re-weighting 重設權重)

這張圖的右半邊 (b) 展示了「重設權重」這個核心步驟：

• 目的：利用 (a) 算出的 $h(v)$ 值，建立一個所有邊權重 $\ge 0$ 的新圖 $\hat{G}$，以便執行 Dijkstra。

• 公式：$\hat{w}(u, v) = w(u, v) + h(u) - h(v)$

• 範例驗證：

  • 邊 $v_1 \to v_2$ (top-left $\to$ top-right):

    • 原始權重 $w = 3$

    • $h(v_1) = 0$, $h(v_2) = -1$

    • $\hat{w} = 3 + 0 - (-1) = 4$。 (你可以在圖 (b) 中看到 $v_1 \to v_2$ 的新權重是 4)

  • 邊 $v_5 \to v_2$ (bottom-left $\to$ top-right):

    • 原始權重 $w = 6$

    • $h(v_5) = -4$, $h(v_2) = -1$

    • $\hat{w} = 6 + (-4) - (-1) = 6 - 4 + 1 = 3$。 (圖 (b) 中 $v_5 \to v_2$ 的新權重是 3)

經過這個步驟，圖 (b) 中的所有邊權重都變成了非負數，Dijkstra 演算法現在可以安全地在這個圖上運作了。

3. 圖 (c) - (g): 步驟 6 (執行 $V$ 次 Dijkstra)

最後這 5 張小圖 (c, d, e, f, g) 展示了演算法的最後階段：

• 目的：在重設權重的圖 (b) 上，從每一個節點 $u$ 出發，各執行一次 Dijkstra 演算法，找出 $u$ 到所有其他節點的最短路徑。

• 圖 (c): 以 $v_1$ (top-left) 為源點，執行 Dijkstra。

• 圖 (d): 以 $v_2$ (top-right) 為源點，執行 Dijkstra。

• 圖 (e): 以 $v_3$ (far-right) 為源點，執行 Dijkstra。

• (以此類推…)

圖上顯示了什麼？

• 粗藍色邊: 代表該次 Dijkstra 運算所找出的「最短路徑樹 (Shortest-Path Tree)」。

• 節點上的標籤 (X/Y): 這是用來顯示最終計算結果的。

  • X = $\hat{\delta}(u, v)$: 使用新權重 $\hat{w}$ (圖 b) 所計算出的最短路徑長度。

  • Y = $\delta(u, v)$: 最終還原的、真正的最短路徑長度 (使用原始權重 $w$)。

    • 這是透過還原公式 (步驟 7) 算出來的： $\delta(u, v) = \hat{\delta}(u, v) + h(v) - h(u)$。

例如，在圖 (c)（Dijkstra from $v_1$）中，節點 $v_3$ 上的標籤 2/-3 (在某些版本的書中，這個數字可能不同，但概念是一樣的)，就代表：

• Dijkstra 在圖 (b) 上找到 $v_1 \to v_3$ 的最短路徑 $\hat{\delta}(1, 3)$ 是 2。

• 還原後的真正最短路徑 $\delta(1, 3)$ 是 -3。

總結

這張圖完整地展示了 Johnson’s 演算法的三大階段：

1. (a) Bellman-Ford: 執行一次，取得 $h(v)$ 值。

2. (b) Re-weighting: 建立一個 $\hat{w} \ge 0$ 的新圖。

3. (c-g) Dijkstra: 在新圖上執行 $V$ 次，並將結果還原，得到全點對最短路徑。