# Bellman-Ford Algorithm
Bellman-Ford 演算法算是比較早期的演算法，而最短路徑問題基本上發展到 Dijkstra 就已經是最佳解了。我們至今還是會用 Bellman-Ford 演算法是因為他可以處理我們無法處理的兩個問題 : 負權邊、找負環

負權邊的問題[上次](https://hackmd.io/@ShanC/Dijkstra)講過了，最短路徑問題[這篇](https://hackmd.io/@ShanC/Shortest-Path)也大概聊過。來說說優點好了，Bellman-Ford 演算法因為本質上是走 walk，而不是 simple path，只要還能鬆弛就能繼續 walk 下去，因此可以幫我們測環

## 邊陣列 Edge Array
這個東西我在[這篇](https://hackmd.io/@ShanC/basic-graph-theory-4)有講過了，但這邊才正式用到，因此再說一次

### 無權邊

pair<int, int> edges[MXN];   // 這裡儲存邊的兩個終點
for(int i = 0; i < m; i++){  // 輸入可以這樣處理
    cin >> edges[i].first >> edges[i].second;
}

### 帶權邊

struct Edge{                 // 儲存兩終點 u, v 與邊的權重 w
    int u, v, w;
}edge[MXN];
for(int i = 0; i < m; i++){  // 輸入可以這樣處理
    cin >> edge[i].u >> edge[i].v >> edge[i].w;
}

## 鬆弛 Relax
由 $\delta$ 的定義，設一起點 $s$，對於任何邊 $(u, v)$ 而言，必須符合三角不等式 :
$$
\delta(s, v)\leq \delta(s, u) + w(u, v)
$$

在單源最短路徑的演算法中，若我們搜尋到的邊不符合三角不等式，我們就需要把它替換掉，就如同我們求最小值的技巧一樣

/* 此為 Pseudocode */
/* d 存兩點之間的最短距離, w 存邊權 */
Relax(u, v, w)
    if d[s][u] > d[u][v] + w[u][v] :
        d[s][u] = d[u][v] + w[u][v]

這個東西是最短路徑的精華

## Bellman-Ford 演算法

### 想法
給一張無負環的圖 $G=(V, E)$、一個邊權函數 $w: E\to \mathbb{Z}$ 與一個起點 $s\in V$。Bellman-Ford 主要的想法是利用鬆弛的機制，每一輪將每條邊都鬆弛。只要鬆弛 $|V|-1$ 輪，那麼距離陣列 $\text{dis}[~]$ 紀錄的就會是最短距離

### 範例

給定以下這張圖，除了起點以外，其他點的 `d[]` 都初始化為 $\infty$

<center>


</center>

從圖中可以發現 $\infty\to\infty$ 是不可能被鬆弛到的，因為都是無限大。僅有從起點出發的邊可以被鬆弛到
<center>


</center>

接下來注意到右邊那個點，他會被兩條邊鬆弛，最後結果為 $\min\{2+4,4+2,\infty\}=6$。而下面的點在這輪也可以被鬆弛，值為 $\min\{4,2-1\}=1$
<center>


</center>

最尾端的點接下來也可以被鬆弛為 $11$。然後會發現因為 $\min\{1+2, 6\}=3$，所以右邊那個點可以被鬆弛

<center>


</center>

由於數值有改變的關係，最後尾端那個點也可以被鬆弛變成 $\min\{11, 3+5\}=8$

<center>


</center>

會發現第 $4$ 輪之後，已經沒有可以鬆弛的邊了

這裡要稍微提醒一下，在例子中，每次鬆弛都是以上一個階段的結果去計算

### 維護最短路徑
這裡 $n=|V|$、$m=|E|$。設第 $t$ 輪鬆弛後，從 $s$ 到其他點 $v$ 的最短距離為 $\text{dis}[t][v]$。那麼其實可以當作 DP 轉移式:

$$
\text{dis}[t][v]=
\begin{cases}
\infty &\text{, if } t=0 \text{ and } v\neq s\\
0 &\text{, if } t=0 \text{ and } v=s\\
\min\limits_{(u,v)\in E}\{\text{dis}[t-1][u]+w(u,v)\} &\text{, if } t\ge 1
\end{cases}
$$

### 程式實作 1
根據以上的定義與想法，可以得到以下程式碼:

for (int t = 0; t < n; t++) {
    for (int i = ; i < m; i++) {
        dis[t][i] = INF; // 很大的數字
    }
}
dis[0][s] = 0;

for (int t = 1; t < n; t++){ // 注意: 這邊只需要跑 n-1 次，而不是 n 次
    for (int i = 0; i < m; i++){
        int u = edge[i].u, v = edge[i].v, w = edge[i].w;
        if (dis[t - 1][u] + w < dis[t][v])
            dis[t][v] = dis[t - 1][u] + w;
    }
}

- 時間: $O(nm)$
- 空間: $O(nm)$

### 程式實作 2
由於當我們跑到第 $t$ 輪時，實際會取用到的資料只有第 $t-1$ 輪的資料，前面 $1\sim t-2$ 都用不到，所以其實可以運用 DP 的 rolling 技巧將空間降一個維度

int dis[2][MXN];
for (int i = 0; i < n; i++) 
    dis[0][i] = dis[1][i] = INF;
dis[0][s] = 0;

for (int t = 1; t < n; t++) {
    int cur = t % 2;
    int prev = (t - 1) % 2;
    
    // 先繼承上一輪的最短路徑結果
    for (int i = 0; i < n; i++) 
        dis[cur][i] = dis[prev][i];
    
    for (int i = 0; i < m; i++) {
        int u = edge[i].u, v = edge[i].v, w = edge[i].w;
        if (dis[prev][u] + w < dis[cur][v]) {
            dis[cur][v] = dis[prev][u] + w;
        }
    }
}

- 時間: $O(nm)$
- 空間: $O(2n)$

### 程式實作 3
其實我們可以通通寫在同一個一維陣列當中。這樣連續覆寫可能會造成連續走很多步，但是這頂多讓某些節點更快速的找到最佳解，所以沒差

for (int t = 1; t < n; t++){ // 注意: 這邊只需要跑 n-1 次，而不是 n 次
    for (int i = 0; i < m; i++){
        int u = edge[i].u, v = edge[i].v, w = edge[i].w;
        if (dis[u] + w < dis[v])
            dis[v] = dis[u] + w;
    }
}

- 時間: $O(nm)$
- 空間: $O(n)$

這種寫法才是真正會用到的程式碼

### 優化
有一種可能就是這張圖其實在第 $n - 1$ 輪鬆弛之前就已經完全鬆弛完。如果真發生這種事，那麼就有好幾輪是浪費的。因此我們可以設一個變數 `relax = true`，來判斷該輪是否還有邊還在鬆弛

bool relax = true;
for(int t = 1; t < n && relax; t++){ 
    relax = false;
    for (int i = 0; i < m; i++){
        int u = edge[i].u, v = edge[i].v, w = edge[i].w;
        if (dis[u] + w < dis[v]) {
            dis[v] = dis[u] + w;
            relax = true;
        }
    }
}

雖然最差情況下時間複雜度相同，但是在某些 case 確實可以加速一下

## 測負環 Negative Cycle Detection

### 想法
不難觀察到，如果存在負環，那麼就可以無限地鬆弛下去，屆時所有距離都是 $-\infty$。這顯然不是我們想要到，因此要找出負環

<center>


</center>

根據最短路徑樹的性質，找出所有點的最短路徑只需要 $n-1$ 輪。若是到第 $n$ 輪還能鬆弛，就到表有環

### 程式實作
用一個變數 `negcycle` 來檢查即可

for (int t = 1; t < n; t++){
    for (int i = 0; i < m; i++){
        int u = edge[i].u, v = edge[i].v, w = edge[i].w;
        if (dis[u] + w < dis[v])
            dis[v] = dis[u] + w;
    }
}

bool negcycle = false;       // 測負環
for (int i = 0; i < m; i++){ // 第 n 輪鬆弛
    int u = edge[i].u, v = edge[i].v, w = edge[i].w;
    if (dis[u] + w < dis[v]) // 還能鬆弛
        negcycle = true;
}

## 備註
- 雖然第 $n$ 輪鬆弛代表存在負環，但是究竟是哪邊有負環，我們並不知道，需要額外再處理。如果是不存在負環的圖，那麼每條邊被鬆弛達到最短後就不會再鬆弛。但如果存在負環的話，在我們鬆弛到負環之後，該負環與後面的節點都會一直被鬆弛
- Bellman-Ford 演算法可以處理的問題是沒有負環的最短路徑
- Bellman-Ford 演算法允許負權邊
- 好像有很多人在差不多同一個時代提出差不多的演算法，但不知道為什麼最後是以 Bellman 跟 Ford 兩人命名

## 題目練習
[CSES Cycle Finding](https://cses.fi/problemset/task/1197)
[CSES High Score](https://cses.fi/problemset/task/1673)
[AtCoder Beginner Contest 061D - Score Attack](https://atcoder.jp/contests/abc061/tasks/abc061_d?lang=en)

----

## 參考資料
- Introduction to Algorithms, Fourth Edition
- [海大 I2CP - Shortest Path](https://hackmd.io/@LeeShoWhaodian/HyT4ib5qJg#/)
- [CP-Algorithms - Bellman-Ford Algorithm](https://cp-algorithms.com/graph/bellman_ford.html)
- [FDHSCPP110 - 最短路徑 shortest path](https://hackmd.io/@fdhscpp110/shortest_path)
- [Aaron - Bellman-Ford algorithm](https://medium.com/algorithm-solving/bellman-ford-algorithm-3cd327630e2d)
- [Wikipedia - Bellman–Ford algorithm](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) (這裡的範例gif檔還蠻不錯的，可以看看)

----

> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2026/1/29