Bellman-Ford 算法

复杂度

时间复杂度： $O (| V | \cdot | E |)$

（ $| V |$ 为顶点数， $| E |$ 为边数）

分析

Dijkstra 算法仅对确定点的出边做松弛操作，Bellman-Ford 算法更为暴力，每次迭代对所有的边做松弛操作，共进行 $| V | - 1$ 次迭代。在重复的计算中，最短路径可以被多次更新，正确最短距离的边随着计算不断增加，直到最后一次迭代，所有的边都计算正确。这也是为什么该算法能够处理赋权边。

伪代码如下：

bellman_ford(G, dist[])
    初始化: dist[1~V]=+INF, dist[1]=0
    for (循环V-1次)
        for (t : 所有边的集合)
            if (以t为中介点到s的距离更短)
                更新dist[s];

迭代次数

上述进行 $| V | - 1$ 次迭代实际上是最大迭代次数，实际有可能在 $| V | - 1$ 次前就已经计算出了所有最短路径。因此可以增加判断，若一次迭代中没有发生松弛操作，即可跳出循环结束算法。

迭代次数实际上也有意义，若进行 $k$ 次迭代，产生的结果便是经过 $\leq k$ 个边的最短路径。因此该算法可以很好地解决“有边数限制的最短路问题”。

负权回路

当图中出现负权回路时，有可能不存在最短路，示例如下：

$B \to D \to C \to \dots$ 为一个回路，该回路的权值为 $1 + (- 2) + (- 1) = - 2$ ，即负权回路。若要求 $A \to E$ 的最短路，我们可以在负权回路中绕任意次，每绕一次路径长度 $- 2$ 。因此 $A \to E$ 的距离可以为 $- \infty$ ，因此不存在最短路径。

若要判断是否有负权回路，可以在 $| V | - 1$ 次后额外进行一次迭代，若第 $| V |$ 次迭代又发生了松弛操作，则可以确定图中存在负权回路。

无穷大判断

由于在代码实现中我们往往使用一个较大的数作为 $\infty$ ，例如 0x3f3f3f3f. 而在该算法中，有可能出现以下松弛操作：

松弛后，后者的值变成了 $\infty - 1$ 。虽然在数学中 $\infty - 1 = \infty$ ，但在程序中 $0x3f3f3f3f$ 不等于 $0x3f3f3f3f - 1$ ，此时对于无穷大的判断就会产生问题。为了规避这个问题，我们可以判断一个数若 $\geq 0x3f3f3f3f / 2$ 就为 $\infty$ ，在一般情况下，是不会出现错误的。

串联问题

在代码实现中，若每次迭代使用的就是本次迭代的值，很有可能产生串联问题，即本次迭代中前面计算出的值被后面的计算使用，这样会产生错误。为了限制本次迭代使用的值一定为上次迭代的值，我们需要备份保存一遍上次的值，对应下面代码中 memcpy 语句。

代码实现

由于该算法只需遍历所有的边即可，所以存图方法比较简单粗暴，直接用一个结构体数组存下来所有边即可。

const int MAXN = 510, MAXM = 1e4 + 10, INF = 0x3f3f3f3f;
int v, e, k;                  // v顶点数 e边数 k经过边数限制
int dist[MAXN], backup[MAXN]; // dist最短距离 backup备份上一次迭代
struct Edge
{
    int a, b, w;              // a起点 b终点 w权值  
} edges[MAXM];                // 结构图数组存边

int bellman_ford()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    for (int i = 0; i < k; i++)
    {
        memcpy(backup, dist, sizeof(dist));
        for (int j = 0; j < e; j++)
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            dist[b] = min(dist[b], backup[a] + w);
        }
    }
    return dist[v] > INF / 2 ? INF : dist[v];
}

算法 | Bellman-Ford 算法