Bellman-Ford 最短路徑

🎯 什麼情境該想到我

當你「圖裡有負權邊，或你需要知道有沒有負權環」的時候。
★ 它比 Dijkstra 最短路徑 慢一個量級，但它能做 Dijkstra 做不到的兩件事：處理負權 和 偵測負權環。

⚙️ 怎麼用（機制與推導）

核心：不挑順序，反覆鬆弛所有邊

1. dist[s] = 0，其餘 = ∞
2. ★ 重複 V-1 輪：
       對「每一條邊」(u,v,w) 都做一次鬆弛
3. ★ 第 V 輪：如果還有邊能被鬆弛 → 存在負權環

和 Dijkstra 的根本差異：

Dijkstra 挑最小的先處理，且「處理過就定案」（貪婪）。
Bellman-Ford 不挑、不定案，只是一輪一輪反覆放寬（動態規劃）。
正因為它不「定案」，所以後來才出現的更短路徑仍然救得回來——這就是它能處理負權的原因。

type edge struct{ from, to, w int }
 
func BellmanFord(edges []edge, n, s int) (dist []int, hasNegCycle bool) {
    const INF = math.MaxInt / 2
    dist = make([]int, n)
    for i := range dist { dist[i] = INF }
    dist[s] = 0
 
    for i := 0; i < n-1; i++ {
        changed := false
        for _, e := range edges {
            if dist[e.from] == INF { continue }        // ★ 不可達的點不要參與鬆弛
            if nd := dist[e.from] + e.w; nd < dist[e.to] {
                dist[e.to] = nd
                changed = true
            }
        }
        if !changed { break }                          // ★ 提前結束：這一輪沒有任何改善
    }
 
    // ★ 第 V 輪還能鬆弛 = 有負權環
    for _, e := range edges {
        if dist[e.from] != INF && dist[e.from]+e.w < dist[e.to] {
            return dist, true
        }
    }
    return dist, false
}

★ 為什麼是「$V-1$ 輪」（必考）

兩步論證：

① 任何最短路徑最多有 $V-1$ 條邊。
最短路徑不會重複經過同一個節點（重複就代表路徑上有環；正權環去掉更短、零權環去掉一樣長）。
$V$ 個節點的簡單路徑最多 $V-1$ 條邊。

② 每跑一輪，至少「確定」最短路上的一條邊。
歸納：第 $k$ 輪結束後，所有「最多 $k$ 條邊」的最短路都已經算對了。

• $k=0$：dist[s]=0 正確
• 第 $k$ 輪會把「$k-1$ 條邊的正確結果」透過一次鬆弛擴展成「$k$ 條邊的正確結果」
  （因為這一輪掃過了所有邊，包含那一條）

①＋② → $V-1$ 輪足夠。

★ 注意論證裡完全沒用到「邊權非負」——這就是它能處理負權的原因。
而 Dijkstra 最短路徑 的正確性證明必須用到非負，所以它不行。

★ 負權環的偵測與意義

如果第 $V$ 輪還能鬆弛成功，代表存在一條「邊數 ≥ $V$」的更短路徑——
由 ① 這在無負環的圖上不可能，所以必定有負權環。

有負權環時，「最短路徑」在數學上不存在（繞環無限次可以無限短）。

實務意義（★ 這才是重點）：

場景	負權環代表什麼
★ 匯率套利	把匯率取 $-\log$ 當邊權，負權環 = 有套利機會（繞一圈回來錢變多）
交易/帳務系統	循環轉帳導致金額不守恆
成本網路	建模錯誤（某條邊的成本被算成負的）
時序約束（差分約束系統）	約束無解——一組不等式互相矛盾

★ 「差分約束系統」是很實用的一招：
形如 $x_j-x_i\le c$ 的一堆不等式，可以轉成邊 $i\to j$ 權重 $c$，
跑 Bellman-Ford 求最短路就得到一組可行解；有負環就代表無解。
用在排程、時序驗證、版本相容性求解。

複雜度

時間	$O(VE)$
空間	$O(V)$

對照：Dijkstra 最短路徑 是 $O(E\log V)$。
$V=10^4,E=10^5$ 時：Bellman-Ford 約 $10^9$、Dijkstra 約 $1.7\times 10^6$ ——差三個數量級。

兩個實務優化

優化	說明
提前結束	某一輪沒有任何鬆弛成功 → 直接結束（見程式碼）。隨機圖上常常幾輪就收斂
★ SPFA（佇列優化）	只把「這一輪 dist 有改變的節點」放進佇列，下一輪只處理它們。 平均快很多，但最差仍是 $O(VE)$，而且在特意構造的圖上會被卡到最差—— ⚠️ 競賽與對外服務中不要依賴 SPFA 的平均效能

🧪 我實際套用的紀錄

• （待填）

⚠️ 注意 / 什麼時候不適用

• ★ 沒有負權就不要用它。$O(VE)$ vs $O(E\log V)$ 差太多——用 Dijkstra 最短路徑。
• ★ 不可達的點不要參與鬆弛：dist[INF] + (-5) 會變成一個比 INF 小的數，污染整張表。程式碼裡的 if dist[e.from] == INF { continue } 不能省。
• INF 不要用 math.MaxInt（溢位）。
• 有負環時 dist 陣列是無意義的，不要拿來用——只能用回傳的 hasNegCycle。
• 要找出負環「本身」（不只是知道有）：在第 $V$ 輪記下被鬆弛的節點，沿 parent 回溯 $V$ 步必定進入環內，再繞一圈即可取出環。
• 有向圖與無向圖不同：無向圖的一條負邊 $u\leftrightarrow v$ 本身就是一個負環（來回走）。所以無向圖 + 負權基本上無解。
• 所有點對的最短路：若 $V$ 不大用 Floyd-Warshall 全對最短路；稀疏大圖用 Johnson 演算法（先跑一次 Bellman-Ford 做「重新賦權」消掉負權，再跑 $V$ 次 Dijkstra）。

🔗 相關工具

• Dijkstra 最短路徑 —— 非負權時的正確選擇，以及它為什麼不能處理負權
• Floyd-Warshall 全對最短路 —— 所有點對，也能偵測負環
• 動態規劃 —— Bellman-Ford 本質上是「以邊數為階段」的 DP
• 廣度優先搜尋 —— SPFA 就是 BFS 式的佇列優化
• 演算法導論