Bellman-Ford Algorithm

預備知識

• Graph
• Dijkstra's Algorithm

Bellman-Ford Algorithm 跟 Dijkstra's Algorithm 一樣，都是用來求「單一起點到其他所有頂點最短路徑」的演算法，但它解決了 Dijkstra 做不到的一件事：圖裡面可以存在負權重的邊。

白話理解

Dijkstra 的邏輯很像「每次都先去確定目前看起來最近的地方，確定了就不再回頭檢查」，一旦路上有一條負權重的邊（例如某條路走了反而倒賺時間），先前「確定」的最短距離就可能被推翻，Dijkstra 完全沒有機制處理這種情況。

Bellman-Ford 換了一個更笨、但更保險的做法：它不相信任何一次的計算結果，而是把所有邊都反覆檢查很多輪，每一輪都問「這條邊能不能讓某個點的距離變得更短？」，直到没有邊能再更新為止。

解析

Bellman-Ford 的核心動作叫 鬆弛（Relaxation）：對於一條邊 u → v（權重為 weight），檢查「經過 u 再走到 v」是不是比「目前記錄的 v」更短：

if distance[u] + weight < distance[v]:
    distance[v] = distance[u] + weight

Bellman-Ford 的做法就是：把圖裡「所有的邊」都拿出來做一次鬆弛，總共重複 V - 1 輪（V 是頂點數量）。

為什麼要跑 V - 1 輪

最短路徑最多只會經過 V - 1 條邊（因為一條合法的最短路徑不會重複經過同一個頂點，V 個頂點之間最多串成 V - 1 條邊）。

每一輪「把所有邊都鬆弛一次」，最壞情況下只能確定「多一條邊長度」的最短路徑，所以跑滿 V - 1 輪之後，理論上所有最短路徑都已經計算完成。

步驟

1. 初始化：起點的距離設為 0，其他所有頂點的距離設為無限遠（Infinity）
2. 重複 V - 1 輪：
   • 每一輪都把圖裡所有的邊都拿出來做一次鬆弛
   • 只要「經過這條邊」比「目前記錄的距離」更短，就更新距離
3. 額外多跑第 V 輪（檢查負權重環）：
   • 如果這一輪還有任何一條邊可以被鬆弛（距離還能變得更短），代表圖中存在負權重環（Negative Cycle），不存在真正的最短路徑

逐步拆解：用一個小範例走一次流程

假設有 4 個頂點 A、B、C、D，邊如下（C → A 帶有負權重）：

A --4--> B
A --5--> C
B --3--> D
C --(-2)--> A
C --3--> D

目標：從 A 出發，算出到其他頂點的最短距離（V = 4，所以要跑 3 輪）。

輪數	依序鬆弛每條邊後的 distances	說明
初始化	A=0, B=∞, C=∞, D=∞	只有起點 A 確定為 0
第 1 輪	A=0, B=4, C=5, D=7	A→B：B 更新為 4；A→C：C 更新為 5；B→D：D 更新為 4+3=7；C→A：0 沒有變短，不更新
第 2 輪	A=0, B=4, C=5, D=7	所有邊再檢查一次，這一輪沒有任何距離被更新，代表已經收斂
第 3 輪	A=0, B=4, C=5, D=7	依然沒有更新，最終答案在第 2 輪就已經確定

這個範例雖然只花了 2 輪就收斂，但 Bellman-Ford 保守地固定跑滿 V - 1 輪，才能保證處理「最壞情況」下的圖（例如一長串必須依序才能鬆弛的邊）。

實作

Python

def bellman_ford(num_vertices, edges, start):
    # edges 是一個 list，每個元素是 (u, v, weight)，代表一條 u -> v、權重為 weight 的邊
    distances = [float("inf")] * num_vertices
    distances[start] = 0

    # 重複 V - 1 輪，每一輪都把所有邊鬆弛一次
    for _ in range(num_vertices - 1):
        for u, v, weight in edges:
            if distances[u] != float("inf") and distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight

    # 多跑一輪：如果還能鬆弛，代表存在負權重環
    for u, v, weight in edges:
        if distances[u] != float("inf") and distances[u] + weight < distances[v]:
            raise ValueError("Graph contains a negative weight cycle")

    return distances

JavaScript

function bellmanFord(numVertices, edges, start) {
  // edges 是一個陣列，每個元素是 [u, v, weight]，代表一條 u -> v、權重為 weight 的邊
  const distances = new Array(numVertices).fill(Infinity);
  distances[start] = 0;

  // 重複 V - 1 輪，每一輪都把所有邊鬆弛一次
  for (let i = 0; i < numVertices - 1; i++) {
    for (const [u, v, weight] of edges) {
      if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
        distances[v] = distances[u] + weight;
      }
    }
  }

  // 多跑一輪：如果還能鬆弛，代表存在負權重環
  for (const [u, v, weight] of edges) {
    if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
      throw new Error("Graph contains a negative weight cycle");
    }
  }

  return distances;
}

Java

class BellmanFord {
    static int[] bellmanFord(int numVertices, int[][] edges, int start) {
        // edges 是一個二維陣列，每個元素是 {u, v, weight}，代表一條 u -> v、權重為 weight 的邊
        int[] distances = new int[numVertices];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[start] = 0;

        // 重複 V - 1 輪，每一輪都把所有邊鬆弛一次
        for (int i = 0; i < numVertices - 1; i++) {
            for (int[] edge : edges) {
                int u = edge[0], v = edge[1], weight = edge[2];
                if (distances[u] != Integer.MAX_VALUE && distances[u] + weight < distances[v]) {
                    distances[v] = distances[u] + weight;
                }
            }
        }

        // 多跑一輪：如果還能鬆弛，代表存在負權重環
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], weight = edge[2];
            if (distances[u] != Integer.MAX_VALUE && distances[u] + weight < distances[v]) {
                throw new IllegalStateException("Graph contains a negative weight cycle");
            }
        }

        return distances;
    }
}

小優化：提早結束

如果某一輪跑完，發現沒有任何一條邊被鬆弛，代表所有距離都已經收斂、不會再變短，可以直接提早跳出迴圈，不需要死板地一定要跑滿 V - 1 輪。

複雜度

項目	複雜度	說明
時間複雜度	O(V × E)	要跑 V - 1 輪，每一輪都要檢查所有 E 條邊
空間複雜度	O(V)	只需要一個陣列記錄每個頂點目前的最短距離

跟 Dijkstra 的 O((V + E) log V) 比起來，Bellman-Ford 明顯慢很多，這也是為什麼「圖裡沒有負權重」時，實務上還是優先選 Dijkstra。

適用情況

• 圖中可能存在負權重的邊：例如金融套利模型中，匯率轉換可能出現「換一圈反而賺錢」的情況，這種帶負權重的場景 Dijkstra 無法處理。
• 需要偵測負權重環：多跑的第 V 輪，如果還能鬆弛，就代表圖中有負權重環，這個特性常被用來判斷「是否存在無限套利的機會」。
• 分散式路由協定：像是 RIP（Routing Information Protocol）這類距離向量路由協定，概念上就是每個節點反覆跟鄰居交換、更新距離資訊，跟 Bellman-Ford 的鬆弛邏輯很相似。
• 圖的規模不大或邊的數量遠小於 V²：因為時間複雜度是 O(V × E)，邊太多時會跑得很慢，這時可以考慮 Shortest Path Faster Algorithm 這個優化版本。

常見誤區

• 誤以為 Dijkstra 一定比 Bellman-Ford好：Dijkstra 確實比較快，但前提是圖裡不能有負權重；只要有負權重的邊，Dijkstra 就可能算出錯誤答案，這時候正確性比速度重要，必須改用 Bellman-Ford。
• 忘記多跑最後一輪來偵測負權重環：只跑 V - 1 輪只能保證「沒有負權重環」時答案正確，如果不確定圖中有沒有負權重環，一定要多跑第 V 輪來確認，否則可能得到一個「看似合理但其實錯誤」的距離。
• 誤以為負權重環一定要回到起點才算數：只要負權重環在「起點可以到達的範圍內」，不管環本身離起點多遠，經過這個環的所有點的最短距離都會是「無限小」（可以無限繞圈讓距離持續下降），並不是只有起點在環上才算數。
• 邊的鬆弛順序想成一定要照圖的拓樸順序：Bellman-Ford 每一輪都是無腦地把所有邊都檢查過一次，不需要事先排好順序，這跟 Topological Sort 那種必須先排好處理順序的做法不一樣。