Bellman-Ford 演算法教學：原理、程式碼與時間複雜度

Bellman-Ford 解決什麼問題

Dijkstra 演算法很快，但要求邊權重非負。有些問題天生就有負權重：退款、匯率兌換中的獲利，或可能低於零的能量成本。Bellman-Ford 能正確處理這類圖，而且當圖中有負環（可以無限繞圈、讓成本越來越低的迴圈）導致不存在最短路徑時，它也會告訴你。

這個演算法以 Richard Bellman 和 Lester Ford Jr. 命名，兩人在 1950 年代分別發表了相關版本。

用白話說明原理

1. 把起點的距離設為 0，其他所有節點設為無限大。
2. 重複 V − 1 次：對每條邊 u → v（權重為 w），如果 dist[u] + w < dist[v]，就更新 dist[v]。
3. 再對所有邊多做一輪。如果仍有距離被改善，就回報存在負環。

為什麼是 V − 1 輪？沒有環的最短路徑最多使用 V − 1 條邊。第 k 輪結束後，最短路徑至多有 k 條邊的節點都已得到正確距離，所以 V − 1 輪就涵蓋了所有簡單路徑。

逐步範例

有向圖有 4 個節點，邊為 S→A（4）、S→B（5）、B→A（−3）、A→C（3）。每一輪都依這個順序處理各條邊。

在第 1 輪中，A 先透過 S→A 變成 4，再經由 B→A 改善為 2，而 C 用的是改善後的值。Dijkstra 演算法會在看到 B 之前就把 A 確定為 4，這正是負權重邊造成的錯誤。

Python 實作

Bellman-Ford 直接處理邊的串列，寫起來很短：

def bellman_ford(nodes, edges, start):
    """edges: list of (u, v, weight). Returns dist, or raises on a negative cycle."""
    INF = float("inf")
    dist = {n: INF for n in nodes}
    dist[start] = 0
    for _ in range(len(nodes) - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                         # already optimal
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            raise ValueError("graph contains a negative cycle")
    return dist
nodes = ["S", "A", "B", "C"]
edges = [("S", "A", 4), ("S", "B", 5), ("B", "A", -3), ("A", "C", 3)]
print(bellman_ford(nodes, edges, "S"))  # {'S': 0, 'A': 2, 'B': 5, 'C': 5}

加入一條權重為 −6 的邊 C → B，會形成環 B → A → C → B，總權重為 −3 + 3 − 6 = −6，因此額外的那一輪就能偵測到它：

try:
    bellman_ford(nodes, edges + [("C", "B", -6)], "S")
except ValueError as e:
    print(e)  # graph contains a negative cycle

dist[u] != INF 這個檢查會略過從尚未到達的節點出發的邊。在 Python 中，float("inf") + w 仍是無限大，所以這個檢查主要是省下運算。在以很大的整數代表無限大的語言中，它能避免溢位和錯誤的更新。

時間與空間複雜度

在 1,000 個節點、10,000 條邊的圖上，最多約需 1,000 萬次鬆弛，所以當權重皆非負時，Dijkstra 快得多。

變化版本與常見錯誤

• 提前結束：當完整一輪都沒有任何變化時就停止。這樣做是安全的，實務上常能大幅加速。
• SPFA（shortest path faster algorithm）：使用佇列，只對距離有變動的節點重新鬆弛其外向邊。通常很快，但最差情況仍是 O(V × E)。
• 限制跳數的路徑：只執行恰好 k 輪，並使用上一輪距離的副本，就能得到最多 k 條邊的最便宜路徑。這可以解決「k 次轉機內的最便宜航班」。
• 找出環本身：維護父節點對應表；當額外那一輪更新了節點 v，就沿著父節點走 V 步，必定會落在環內，再繼續走直到回到同一個節點。

何時使用與實際應用

• 當邊權重可能為負，或必須偵測負環時，請使用 Bellman-Ford；否則優先選擇 Dijkstra。
• 距離向量路由協定（例如 RIP）使用的是分散式 Bellman-Ford 的概念：每個路由器根據鄰居的估計值，不斷更新自己的距離估計。
• 匯率套利：把權重設為 -log(rate)，負環就代表一連串的兌換最後得到比起始更多的錢。
• Johnson 演算法先執行一次 Bellman-Ford 對圖重新加權，之後就能從每個節點執行 Dijkstra，求出所有節點對的最短路徑。
• 差分約束（形如 x - y <= c 的不等式系統）可以轉換成最短路徑問題求解；出現負環就代表無解。