Bellman-Ford：負邊也能算最短路

為什麼需要它？

第 14 章 Dijkstra 講過：權重不能是負數。

但現實有負邊的情境：

套利交易（買賣有正負利潤）
任務 reward 可正可負
物理模擬（位能差）

Bellman-Ford 不怕負邊，而且還能告訴你「有沒有負環」（會無限變便宜的圈）。

核心想法：暴力鬆弛 V-1 次

最短路徑最多用 V-1 條邊（不然會有環，環在最短路只會浪費）。 所以鬆弛 V-1 次，每次嘗試對所有邊做一次 relaxation——就一定能算出最短距離。

Relaxation（鬆弛） = 「如果走過 u 再到 v 比直接到 v 更近，就更新」：

if dist[u] + weight(u, v) < dist[v]:
    dist[v] = dist[u] + weight(u, v)

跑一遍

圖：4 個點 A, B, C, D，邊：A→B(4)、A→C(2)、B→C(-3)、C→D(2)、B→D(5)。起點 A。

初始：dist = [A:0, B:∞, C:∞, D:∞]

輪	鬆弛動作	dist 變化
1-1	A→B: 0+4=4 < ∞ → 更新	B=4
1-2	A→C: 0+2=2 < ∞ → 更新	C=2
1-3	B→C: 4-3=1 < 2 → 更新	C=1 ✨負邊救援！
1-4	C→D: 1+2=3 < ∞ → 更新	D=3
1-5	B→D: 4+5=9 ≥ 3 → 不動	—
2-1	跑同樣的邊一輪，沒有更新 → 收斂	dist=[0,4,1,3] ✓

跑 V-1=3 輪即停（沒更新可以提早結束）。

💡為什麼 V-1 輪一定夠？

最短路徑最多 V-1 條邊（簡單路徑）。第 k 輪後，所有「最多用 k 條邊」的最短距離一定算對了。所以 V-1 輪後，所有最短距離都算對。

Pseudocode

Algorithm BellmanFord(graph, source):

dist[v] ← ∞ for v in V

dist[source] ← 0

for i ← 1 to V-1:

for (u, v, w) in edges:

if dist[u] + w < dist[v]:

dist[v] ← dist[u] + w

// 第 V 輪還能更新 → 有負環

for (u, v, w) in edges:

if dist[u] + w < dist[v]:

return “Negative cycle detected”

return dist

偵測負環

第 V 輪如果還能更新 → 有負環。

直覺：V-1 輪後應該收斂，再跑一輪還能變更短 → 一定有「越走越便宜」的環。

複雜度

	Big-O
時間	O(V × E)
空間	O(V)

比 Dijkstra 的 O((V+E) log V) 慢得多。密集圖 V=1000, E=10⁶ → 10⁹ 操作，跑不完。

Bellman-Ford vs Dijkstra

	Bellman-Ford	Dijkstra
負邊	支援 ✓	❌
偵測負環	支援 ✓	—
時間	O(V × E)	O((V+E) log V)
實作	簡單（兩層 for）	需 priority queue

用對工具：沒負邊就用 Dijkstra，有負邊才用 Bellman-Ford。

經典應用：套利

外匯：USD → JPY → EUR → USD，如果最後 USD 變多了，就有套利機會。

把匯率取 log，負對數 = 邊權重，套利機會 = 圖上有負環。 Bellman-Ford 跑一遍就能偵測。

📝考試會這樣考

題型一：跑一遍 Bellman-Ford。 給帶權圖（含負邊）和起點，列出每輪後的 dist 陣列。訣竅：表格列頂端寫每個節點，每輪列出所有 dist 值。

題型二：偵測負環。 跑第 V 輪，看有沒有更新。有 → 有負環。

題型三：為什麼 Dijkstra 不能處理負邊？ 答：Dijkstra 假設「一旦處理某點，最短距離就確定」，但負邊可能讓「後來才發現更短的路」，違反假設。

題型四：Bellman-Ford 跟 DP 有什麼關係？ 答：它就是 DP。狀態 dp[k][v] = 用最多 k 條邊到 v 的最短距離。轉移：dp[k+1][v] = min(dp[k][v], min_u(dp[k][u] + w(u,v)))。空間壓成一維就是 Bellman-Ford。

題型五：時間複雜度為什麼是 O(V × E)？ 答：外層 V-1 輪，內層走訪所有 E 條邊做 relaxation。

這章記住

Bellman-Ford 能處理負邊，代價是 O(V × E) 比 Dijkstra 慢。
跑 V-1 輪 relaxation 一定收斂。
第 V 輪還能更新 → 有負環。
沒負邊請用 Dijkstra，只有負邊才需要 Bellman-Ford。