Bellman Ford

对于一条从$u$到$v$长度为$w$的边，最终的最短路一定满足$d_v \leq d_u + w$否则$d_v$还可以被更新为$d_u + w$，这也叫做松弛操作。

循环$n$次，对每条边$j$进行松弛操作，便可以得到每个点的最短路。

for (int i = 0; i < n; i++) // 循环n次
{
    for (int j = 0; j < m; j++) // 每次中，循环第j条边，第j条边的起点是 u[j] 终点是 v[j] 边长是 w[j]
    {
        // d[v[j]] = min(d[v[j]], d[u[j]] + w[j]); // 如果 终点的距离 大于 起点的距离 加 边长 ，那么更新
        if (d[v[j]] > d[u[j]] + w[j])
        {
            d[v[j]] = d[u[j]] + w[j];
        }
    }
}

特别的，如果第$n$轮更新（即$i = n - 1$时）发生了松弛操作，那么说明某个点的最短路上存在$n$条边，这是不可能的，一定有负环的存在。

Bellman Ford

https://en.wikipedia.org/wiki/Bellman–Ford_algorithm

Time O(nm)
时间复杂度 O(nm)

Relax Operation
松弛操作

if (dist[edge_end] > dist[edge_start] + edge_length)
{
    dist[edge_end] = dist[edge_start] + edge_length;
}

如果一条边终点的距离 大于 起点的距离 加 边的长度
把终点的距离 改成 起点的距离 加 边的长度

n is the number of vertices.
如果 n 是图的点数

There are at most n-1 edges on the shortest path.
那么最短路上至多有 n-1 条边

如果最短路上有n条边
就意味着某个点到过2次
就意味着出环了（长度为0的环或者长度为负数的环）

for (int i = 0; i < n; i++) // n-1 times 循环 n-1 次
{
    bool changed = false;
    for (int j = 0; j < m; j++) // all edges 枚举所有的边
    {
        // Relax Operation 松弛操作
        if (dist[end[j]] > dist[start[j]] + length[j])
        {
            dist[end[j]] = dist[start[j]] + length[j];
            changed = true;
        }
    }
    // 如果枚举所有的边，没有进行松弛操作，那么退出
    if (!changed)
    {
        break;
    }
}

P1938 [USACO09NOV]Job Hunt S

d[i] largest income ending at vertex i.

if (dist[edge_end] < dist[edge_start] + edge_length)
{
    dist[edge_end] = dist[edge_start] + edge_length;
}

如果最短路上有n条边，那么这个图中有负环
If there are n edges on the shortest path, then there is a negative-weight cycle.
USACO Heat Wave