單一起點最短路徑

Single-Source Shortest Paths 演算法總覽

項目	DAG（Directed Acyclic Graph）	Dijkstra	Bellman–Ford
解決問題	單源最短路	單源最短路	單源最短路
策略	拓樸排序（Topological sort）	貪婪（Greedy）	動態規劃（反覆鬆弛）
圖可有 cycle	否（必須為 DAG）	是	是
圖可有負權邊（negative edge）	是	否	是
圖可有負環（negative cycle）	否	否	否（若存在則回報）
時間複雜度（鄰接矩陣）	\(O(V+E)\)	\(O(V^2)\)	\(O(V^3)\)
時間複雜度（鄰接串列／堆）	\(O(V+E)\)	\(O(E\log V)\)（binary heap）；\(O(V\log V+E)\)（Fibonacci heap）	\(O(VE)\)

Relax

若經由 \(u\) 可以改進 \(v\) 的估計，就更新距離與前驅：

RELAX(u, v):
  if v.d > u.d + w(u,v):
	  v.d = u.d + w(u,v)
	  v.π = u

伴隨性質：
1. 上界：\(v.d \ge \delta(s,v)\)，一旦等於就不再變。
2. 三角：\(\delta(s,v)\le \delta(s,u)+w(u,v)\)。
3. 收斂：若 \(u.d=\delta(s,u)\)，鬆弛 \((u,v)\) 後得 \(v.d=\delta(s,v)\)。

DAG shortest-paths algorithm

問題與條件：單源最短路，圖為 DAG。允許負邊；無（負）環。輸入 \(G=(V,E),\ w:E\to\mathbb{R},\ s\in V\)。
核心觀念：拓樸序一次走完，對每條邊恰鬆弛一次，總時間 \(O(V+E)\)。
DAG shortest-paths（列表版流程）
- 取得拓樸序列 \(L\)（\(O(V+E)\)）。
- 依序掃 \(L\) 中每個 \(u\)。
- 對 \(u\) 的每條外出邊 \((u,v)\) 呼叫 RELAX(u,v)。

演算法

初始化

 for all v ∈ V: v.d = ∞, v.π = NIL
 s.d = 0

演算法本體

取得拓樸序列 \(L=\text{TOPOLOGICAL SORT}(G)\)。
初始化單源。
依序掃 \(L\) 中每個 \(u\)；對每條外出邊 \((u,v)\) 執行 RELAX(u,v)。

 DAG_SHORTEST_PATHS(G, w, s)
   L ← TOPOLOGICAL_SORT(G)        // O(V+E)
   for each v ∈ V: v.d ← ∞; v.π ← NIL
   s.d ← 0
   for each u in L: // 針對所有 adj list 的每個點去做 Relax
 	  for each (u, v) ∈ adj[u]:
 		  RELAX(u, v)

複雜度：拓樸排序 \(O(V+E)\)；每邊鬆弛一次 \(O(E)\)；合計 \(O(V+E)\)。空間 \(O(V)\)。
可與不可
- 可：負邊。
- 不可：任意環（DAG 定義使然），因此不會有負環。
輸出讀法
- 距離：\(v.d\)（不可達則 \(=\infty\)）。
- 路徑：從 \(v\) 逆著 \(v.π\) 回溯到 \(s\)。
對照 Dijkstra
- Dijkstra 要求邊非負，時間常見 \(O(E\log V)\)；適用一般圖。
- DAG 法更快 \(O(V+E)\)，但僅限 DAG。

範例

Dijkstra Algorithm

資料結構版本 `adj matrix`

資料結構
- 成本矩陣：\(COST[i,j] =\) \(\begin{cases}邊權 ,w(i,j)，若 (i,j)\in E \\ \infty，若 (i,j)\notin E\\ 0，若 i=j。\end{cases}\)
- 布林陣列：\(S[1..n]\)（是否「定稿」）。
- 距離陣列：\(DIST[1..n]\)（目前最短估計）。
- 可選：\(P[1..n]\)（前驅，用來回溯路徑）。
初始化（源點 \(s\)）
- 對所有 \(i\)：\(S[i]=false\)，\(DIST[i]=COST[s,i]\)。
- \(S[s]=true\)，\(DIST[s]=0\)，\(P[s]=NIL\)。
核心步驟（重複直到全數定稿）
- 選 \(u=\min{DIST[i]\mid S[i]=false}\)。
- 設 \(S[u]=true\)（此時 \(DIST[u]=\delta(s,u)\) 已定）。
- 對所有尚未定稿的 \(v\)：若 \(DIST[v] > DIST[u] + COST[u,v]\)，則
  \(DIST[v] = DIST[u] + COST[u,v]\)，\(P[v]=u\)。
矩陣版 Pseudocode（\(O(n^2)\)）

DIJKSTRA_MATRIX(COST, n, s)
  for i = 1..n:
	  S[i]    = false
	  DIST[i] = COST[s, i]
	  P[i]    = (COST[s, i] < ∞ and i ≠ s) ? s : NIL
  S[s] = true
  DIST[s] = 0

  repeat (n-2) times:
	  u = argmin_i { DIST[i] | S[i] = false }       // O(n)
	  S[u] = true
	  for v = 1..n:                                 // 掃一整列 O(n)
		  if S[v] = false and COST[u, v] < ∞ and DIST[v] > DIST[u] + COST[u, v]:
			  DIST[v] = DIST[u] + COST[u, v]
			  P[v] = u

時間與空間
- 每輪找 \(u\) 掃一遍頂點 \(O(n)\)；鬆弛掃一整列 \(O(n)\)；共 \(n-1\) 輪 ⇒ \(O(n^2)\)。
- 空間：矩陣 \(O(n^2)\)，\(DIST,S,P\) 各 \(O(n)\)。
- 適合稠密圖或沒有堆結構時的教學實作；稀疏圖建議「鄰接串列 + 最小堆」版本，時間 \(O((V+E)\log V)\)。
必要條件與產出
- 權重限制：\(w(i,j)\ge 0\)。
- 結束後：\(DIST[v]=\delta(s,v)\)；由 \(P[v]\) 回溯得最短路徑樹。
不變式小抄
- 上界：對所有 \(v\)，\(DIST[v]\ge \delta(s,v)\)。
- 正確性：每次選出的 \(u\) 滿足 \(DIST[u]=\delta(s,u)\)，之後不再改變。
- 鬆弛充足：矩陣版每回合檢查所有 \(v\)，不會漏掉可改進的鄰接。

演算法版本

複雜度分析

前提：以鄰接串列表示圖，\(w(u,v)\ge 0\)。優先佇列 \(Q\) 存所有頂點，鍵為 \(v.d\)。
成本分解
- 初始化 INITIALIZE-SINGLE-SOURCE：\(O(V)\)。
- 建立空的最小優先佇列 \(Q\) 並把頂點放入：\(O(V)\)。
- 重複 EXTRACT-MIN(Q) 共 \(V\) 次：每次 \(O(\log V)\) ⇒ \(O(V\log V)\)。
- 外層 for/while 會掃過所有邊一次（針對每個 \(u\) 的鄰接串列）：總計 \(E\) 次檢查。
- 對每條邊觸發一次 DECREASE-KEY：
  - Binary heap：每次 \(O(\log V)\) ⇒ \(O(E\log V)\)。
  - Fibonacci heap：每次攤銷 \(O(1)\) ⇒ \(O(E)\)。
總時間
- 若 \(Q\) 用 binary heap：\(O(V)\)（初始化） \(+\) \(O(V\log V)\)（extract） \(+\) \(O(E\log V)\)（decrease-key）
  ⇒ \(O((V+E)\log V)\)（常見寫法也可記成 \(O(E\log V)\)）。
- 若 \(Q\) 用 Fibonacci heap：\(O(V)\) \(+\) \(O(V\log V)\) \(+\) \(O(E)\)
  ⇒ \(O(V\log V + E)\)。
備註：若用鄰接矩陣且不建堆，經典實作為 \(O(V^2)\)。

Dijkstra’s Algorithm 不能用在含負權邊的圖

條件：來源 \(A\)；邊權：\(A\to B=3,\ A\to C=5,\ C \to B=-4,\ B\to D=1\)。
關鍵：Dijkstra 會把先彈出的頂點視為「定稿」。若之後經由負邊能把它再變更小，演算法不會回頭改，因而錯誤。
示例最短路：\(A\to C \to B \to D\) 長度 \(5+(-4)+1=2\)，但 Dijkstra 會輸出 \(A \to B \to D\) 長度 \(4\)。
正確做法：含負邊用 Bellman–Ford；可偵測負環。
一步步（精簡版）
1. 初始：\(B.d=3,\ C.d=5,\ D.d=\infty\)。
2. 取出 \(B\) 定稿，鬆弛 \(B \to D\) 得 \(D.d=4\)。
3. 取出 \(D\) 無事可做；再取出 \(C\)，鬆弛 \(C \to B\) 得 \(1<3\)，但 \(B\) 已定稿，不會改。
4. 結束；輸出錯誤的 \(4\)。

Bellman-ford Algorithm

定義

採用 DP 的方式
\(k\) 表示允許的邊數上限。
定義 \(\mathrm{Dist}^k[i]\) 為：從起點 \(s\) 到頂點 \(i\)、最多使用 \(k\) 條邊的最短距離。
則遞迴式：

\mathrm{Dist}^k[i] =\min\Big( \underbrace{\mathrm{Dist}^{k-1}[i]}_{\text{路徑不增邊，走原路}}, \ \underbrace{\min_{(j,i)\in E}\big(\mathrm{Dist}^{k-1}[j]+ \mathrm{cost}[j,i]\big)}_{\text{經由某前驅 $j$ 多走一條邊做 relaxation，更好就更新 }(j,i)} \Big).

理由：用最多 \(k\) 邊到 \(i\) 的最短路，只可能是
1. 不用第 \(k\) 條邊，與 \(k-1\) 邊解相同；或
2. 恰用 \(k\) 條邊，最後一步走 \((j,i)\)，其代價是到 \(j\) 的 \(k-1\) 邊最短路加上 \(\mathrm{cost}[j,i]\)。
步驟
1. 初始：\(\mathrm{Dist}^0[s]=0,\ \mathrm{Dist}^0[i\ne s]=\infty\)。
2. 重複 \(k=1\ldots |V|-1\) 即得 \(\mathrm{Dist}^{|V|-1}\) 為答案（任何簡單路徑至多 \(|V|-1\) 邊）。
3. 再做一次鬆弛仍能下降則存在負環。

演算法實作

DS 版本

用途：單源最短路，允許負邊；可偵測負環。
輸入：頂點數 \(n\)，源點 \(s\)，成本矩陣 \(COST[1..n,1..n]\)
（\(COST[i,j]=w(i,j)\)；若無邊則 \(=\infty\)；\(COST[i,i]=0\)）。
輸出：\(DIST[v]=\delta(s,v)\) 與 \(P[v]\)（前驅）；若有負環則回報。

BELLmanFord_MATRIX(COST, n, s)
  # 初始化 O(n)
  for i = 1..n:
      DIST[i] = COST[s,i]        # s 到 i 的一跳估計
      P[i]    = (COST[s,i] < ∞ and i ≠ s) ? s : NIL
  DIST[s] = 0

  # 主要迴圈：做 (n-1) 輪鬆弛；矩陣版每輪掃所有有向邊 O(n^2)
  for k = 1..(n-1):
      for u = 1..n:
          for v = 1..n:
              if  DIST[v] > DIST[u] + COST[u,v]:
                  DIST[v] = DIST[u] + COST[u,v]
                  P[v]    = u

  # 第 n 輪檢查是否仍可改善 → 有可達負環
  hasNegCycle = false
  for u = 1..n:
      for v = 1..n:
          if DIST[v] > DIST[u] + COST[u,v]:
              hasNegCycle = true   # s 可達的負環存在
  return (DIST, P, hasNegCycle)

時間：矩陣版掃邊 \(n^2\) 次、共 \(n-1\) 輪 ⇒ \(O(n^3)\)。
鄰接串列版為 \(O(VE)\)。
正確性關鍵：在無可達負環時，任一路徑最多含 \(n-1\) 條邊；逐輪把長度 \(\le k\) 的最佳路徑推進到第 \(k\) 輪收斂。
路徑輸出：對任一 \(t\)，自 \(t\) 逆著 \(P[\cdot]\) 回溯到 \(s\)。

CLRS 版本

時間複雜度 \(O(VE)\)，那麼是因為 base on adj list

Single-Source Shortest Paths 演算法總覽

Relax

DAG shortest-paths algorithm

範例

Dijkstra Algorithm

資料結構版本 adj matrix

演算法版本

複雜度分析

Dijkstra’s Algorithm 不能用在含負權邊的圖

Bellman-ford Algorithm

定義

演算法實作

DS 版本

CLRS 版本

範例

資料結構版本 `adj matrix`