在前一天我們介紹了 Dijkstra 演算法，它能有效解決 單源最短路徑 (Single Source Shortest Path, SSSP) 問題，但有一個限制: 不能處理負權重邊 (Negative Weights)。然而，現實世界的很多問題 (例如金融套利、債務網路、價格波動) 都可能出現負權重，這時候我們就需要 Bellman-Ford 演算法。

演算法背景

• 發明者: Richard Bellman 與 Lester Ford (1958)
• 適用場景
  • 圖可能含有負權重邊
  • 需要檢測 負權重環 (Negative Weight Cycle)
• 與 Dijkstra 的差異
  • Dijkstra 每次「貪心」取最短距離更新 → 高效，但不能處理負邊
  • Bellman-Ford 採用「動態規劃」思想，不斷鬆弛邊，最終收斂到最短路徑

核心思想

Bellman-Ford 的核心是 邊鬆弛 (Relaxation):
對於一條邊 $(u, v)$ 以及權重 $w(u, v)$，如果:

$$
dist[v] > dist[u] + w(u, v)
$$

則更新:

$$
dist[v] = dist[u] + w(u, v)
$$

演算法步驟

• 初始化
  • 對所有節點距離 dist[v] = ∞
  • 起點 dist[start] = 0
• 鬆弛操作
  • 重複 V-1 次 (V 為節點數)
  • 每次遍歷所有邊，嘗試更新距離
• 檢測負權重環
  • 再做一次鬆弛，如果還能更新，代表存在 負權重環

Python 程式碼

def bellman_ford(graph, V, start):
    # graph: list of edges [(u, v, w), ...]
    # V: 節點數量
    dist = [float('inf')] * V
    dist[start] = 0
    
    # Step 1: 鬆弛 V-1 次
    for _ in range(V - 1):
        for u, v, w in graph:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    
    # Step 2: 檢查是否有負權重環
    for u, v, w in graph:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            print("圖中存在負權重環")
            return None
    
    return dist


# 測試
V = 5
edges = [
    (0, 1, -1),
    (0, 2, 4),
    (1, 2, 3),
    (1, 3, 2),
    (1, 4, 2),
    (3, 2, 5),
    (3, 1, 1),
    (4, 3, -3)
]

print(bellman_ford(edges, V, 0))
# 輸出: [0, -1, 2, -2, 1]

複雜度分析

• 時間複雜度: $O(V \times E)$
• V 為節點數，E 為邊數
• 適合邊數不多 (Sparse Graph) 的圖
• 空間複雜度: $O(V)$

與 Dijkstra 相比:

• Dijkstra：$O((V+E)\log V)$ (效率更高)
• Bellman-Ford：$O(VE)$ (效率較差)

但 Bellman-Ford 能處理 負權重與負環檢測，這是它最大的優勢。

結語

Bellman-Ford 演算法雖然比不上 Dijkstra 的高效率，但它能處理負權重邊，並且能檢測負權重環，這讓它在特定情境下不可或缺。如果你的問題環境可能存在負邊，就必須使用 Bellman-Ford。