所有點對最短路徑

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\)）。

  • 遞迴：

• 直觀：考慮是否讓 \(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\) 次，並將結果還原，得到全點對最短路徑。