Bellman-Ford含負權最短路徑

01為什麼需要它

看到這些關鍵字就想到它：邊有負權、負環、套利、最多經過 k 條邊、距離向量路由、差分約束 x_j − x_i ≤ c、Dijkstra 不能用的最短路徑、V 和 E 都不大。

02核心概念

Bellman-Ford 不挑順序，也不確定任何節點，只做一件事：把所有邊全部鬆弛一遍，稱為一輪，然後重複。dist 一開始除了起點都是 ∞，每一輪對每條邊 u → v 檢查 dist[u] + w < dist[v]，成立就更新。它的保證是：做完第 k 輪，dist[v] 不超過「最多用 k 條邊」到 v 的最短距離。用歸納法看：最多 k+1 條邊的最短路徑，前 k 條邊到達的節點 u 在第 k 輪結束時 dist 已經不超過那段的長度，第 k+1 輪掃到最後那條邊 u → v 時就會把 dist[v] 壓下來。

沒有負環時，最短路徑一定是簡單路徑（繞圈只會變長或不變），最多 V − 1 條邊，所以 V − 1 輪之後 dist 就是正確答案。這個論證完全沒用到「邊權非負」，因此負權邊沒有問題。Dijkstra 不行，是因為它在節點取出時就把距離定案，假設之後不可能出現更短的路；有負權邊時，晚一點才走到的路可能反而更短。以示範的圖為例，取出即定案的 Dijkstra 會把 A 定在 6、D 定在 2，實際最短是 2 和 −2。

負環偵測：若從起點走得到一個總權重為負的環，就能繞著它無限變短，最短路徑沒有定義。這時第 V − 1 輪之後一定還有邊能鬆弛（否則沿著環把不等式加起來會得到環的總權重 ≥ 0，矛盾），所以多掃第 V 輪，還能更新就是有負環。要找出環本身，記下第 V 輪被更新的節點，沿 parent 往回走 V 步，保證已經踩在環上，再走一圈就能收集環上的節點。複雜度是 V 輪乘上每輪 E 條邊，O(VE) 時間、O(V) 空間；一整輪都沒有更新時可以提前結束，實務上常常遠少於 V − 1 輪。SPFA 用佇列只重新檢查距離剛變小的節點，平均快很多，但最壞情況一樣 O(VE)，也有專門讓它變慢的輸入。

常見的坑：從 dist = ∞ 的節點出發鬆弛，∞ 加上負權仍然是很大的數，卻可能被當成「更短」，所以一定要先檢查 dist[u] != ∞，C++ 的 INF 也要留空間避免溢位；無向圖裡的一條負權邊本身就是負環（u → v → u）；只想偵測「任何地方」的負環，就把所有 dist 設成 0（等於加一個連到每個節點的虛擬起點）；限制「最多 k 條邊」（LeetCode 787）時，每一輪必須只用上一輪的距離，否則同一輪裡可能連走好幾條邊。怎麼選：邊權非負用 Dijkstra；圖是 DAG 時先拓撲排序再鬆弛，O(V + E) 而且負權也行；要任兩點的距離而且 V 不大，用 Floyd-Warshall。

03演算法步驟

1. 1dist 全部設為 ∞，dist[src] = 0。把圖存成邊的列表 (u, v, w) 就夠了。
2. 2重複 V − 1 輪：對每條邊，若 dist[u] != ∞ 且 dist[u] + w < dist[v]，就更新 dist[v]，需要路徑時同時記 parent[v] = u。
3. 3某一輪完全沒有更新，就代表已經收斂，可以提前結束。
4. 4再掃一輪所有邊：還有邊能鬆弛，表示存在從起點走得到的負環，最短路徑沒有定義。
5. 5要找出負環：記下這一輪被更新的節點，沿 parent 往回走 V 步，再繞一圈收集節點。限制最多 k 條邊時，每一輪只用上一輪的 dist 複本來鬆弛。

04互動示範

五個節點、十條有向邊，負權的邊權數字標成黃色。「例子 1：有負邊、無負環」：第 1 輪就更新了六次，第 2 輪只剩 A → D 把 D 從 2 壓到 −2，第 3 輪沒有任何更新，提前結束，最後 A = 2、D = −2。「例子 2：有負環」把 C → A 改成 −5，A → D → C → A 繞一圈總和變成 −2：每一輪都還在更新，連起點 S 都被壓到負數，做完 4 輪後的第 5 輪檢查仍能鬆弛，沿 parent 找出的負環 C → A → D → C 以黃色標出。節點方面，藍色是這一步被更新的節點，黃色是已經有距離、但之後可能再變的節點；藍色的邊是本輪鬆弛成功的邊。

05程式碼

Python 放標準的 Bellman-Ford（含提前結束與負環判斷）、找出負環本身，以及「最多用 k 條邊」的變形，範例用互動示範的同一張圖。C++ 放 Bellman-Ford 與 SPFA 兩種寫法，負環判斷各用一種：Bellman-Ford 看第 V 輪還能不能鬆弛，SPFA 看某條最短路徑是否用到了 V 條邊。

from math import inf


def bellman_ford(n, edges, src):
    """edges 是有向邊 (u, v, w)。回傳 (dist, 是否有從 src 走得到的負環)。O(VE)"""
    dist = [inf] * n
    dist[src] = 0
    for _ in range(n - 1):                    # 沒有負環時，最短路徑最多 n − 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
    has_neg_cycle = any(dist[u] != inf and dist[u] + w < dist[v] for u, v, w in edges)
    return dist, has_neg_cycle


def find_negative_cycle(n, edges):
    """回傳任一個負環上的節點（依邊的方向），沒有負環回傳 None"""
    dist = [0] * n                            # 全設 0：等於有個虛擬起點連到每個節點
    parent = [-1] * n
    for _ in range(n):
        x = -1
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v], parent[v], x = dist[u] + w, u, v
    if x == -1:
        return None                           # 第 n 輪沒有任何更新：沒有負環
    for _ in range(n):
        x = parent[x]                         # 往回走 n 步，一定已經踩在環上
    cycle, y = [x], parent[x]
    while y != x:
        cycle.append(y)
        y = parent[y]
    return cycle[::-1]


def shortest_with_k_edges(n, edges, src, k):
    """最多只能用 k 條邊（例如最多轉機 k − 1 次）"""
    dist = [inf] * n
    dist[src] = 0
    for _ in range(k):
        prev = dist[:]                        # 只用上一輪的值，同一輪不能連走好幾條邊
        for u, v, w in edges:
            if prev[u] != inf and prev[u] + w < dist[v]:
                dist[v] = prev[u] + w
    return dist


if __name__ == "__main__":
    S, A, B, C, D = range(5)                  # 和互動示範同一張圖
    edges = [(S, A, 6), (S, B, 7), (A, C, 5), (A, B, 8), (A, D, -4),
             (B, C, -3), (B, D, 9), (C, A, -2), (D, C, 7), (D, S, 2)]
    print(bellman_ford(5, edges, S))          # ([0, 2, 7, 4, -2], False)
    print(shortest_with_k_edges(5, edges, S, 2))   # [0, 6, 7, 4, 2]（只准走 2 條邊）

    neg = [(u, v, -5 if (u, v) == (C, A) else w) for u, v, w in edges]
    print(bellman_ford(5, neg, S)[1])         # True
    print(find_negative_cycle(5, neg))        # [4, 0, 2, 3, 1]：D→S→B→C→A→D 總和 −3
    # 示範找到的是 C→A→D→C（−2）：同一張圖可以有好幾個負環，找到哪個取決於掃描順序

06練習題

• LeetCode 743Network Delay Time（邊權非負，用 Bellman-Ford 再寫一次和 Dijkstra 對照）Medium
• LeetCode 787Cheapest Flights Within K Stops（最多 k+1 條邊，每輪只用上一輪的距離）Medium
• CSES 1197Cycle Finding（找出並印出一個負環）Medium
• LeetCode 1928Minimum Cost to Reach Destination in Time（依時間分層鬆弛）Hard
• CSES 1673High Score（最長路徑：邊權取負，只看走得到終點的負環）Hard