贝尔曼福特算法

贝尔曼福特算法 Bellman-Ford Algorithm

Bellman-Ford 算法也是一种用于求解单源最短路径问题的算法，特别适用于含有负权边的图。与 Dijkstra 算法不同，Bellman-Ford 算法能够检测到负权重环路的存在。

Bellman-Ford 的算法思想是通过 松弛操作 (Relaxation) 逐步找到从源点到所有其他顶点的最短路径。对一条边进行松弛操作指的是检查一条边/图上的路径是否能提供更短的路径。如果可以，那么就更新答案。

该算法会重复对图中的所有边进行松弛操作，总共执行 $\lvert V\rvert - 1$ 次，其中 $\lvert V\rvert$ 是图中顶点的数量。

Bellman-Ford 算法具体的实现流程如下：

1. 初始化：

• 创建一个数组，用于记录从源点开始到任意一点的距离。同时设定源节点的距离为 $0$，其他所有节点的距离为 $+\infty$​。

2. 松弛操作：

• 对于每一条边 $(u, v)$，和这条边的权重 $w(u, v)$，如果可以使得 $dis_u + w(u, v) < dis_v$，则将 $dis_v$ 更新为 $dis_u + w(u, v)$。其中，$dis_i$ 表示编号为 $i$ 节点的距离。
• 重复上述步骤 $\lvert V\rvert - 1$ 次。

3. 检测是否存在负环：

• 再次对所有边执行松弛操作。如果发现某条边 $(u, v)$ 仍能使 $dis_u + w(u, v) < dis_v$ 成立，则说明图中存在负权重环路。
• 换句话说，如果一个图不存在负环，则这张图的边在经历最多 $\lvert V\rvert - 1$ 次松弛操作后将不能再进行松弛了。

以下是使用 Bellman-Ford 算法对例题的模拟过程：

首先初始化距离数组，将源点的距离设置为 $0$，将除源点以外的所有点的距离设置为 $+\infty$。正无穷大表示到达该点的最短距离还未知。

选择一条边，对该边尝试进行一次松弛操作。如下图（红色的边表示当前选中的边），通过这一条边可以将从源点到 $2$ 号点的距离从正无穷大缩短至 $2$，因此更新新的距离。

以次类推，依次遍历并尝试松弛所有的边。当每一条边经历 $\lvert V\rvert - 1$ 次松弛操作后，算法结束。此时距离数组记录的值就是从源点出发到各个点的最短距离。

完整的 Bellman-Ford 求解最短路的代码如下（对应例题：洛谷 - P4779 【模板】单源最短路径（标准版） 和 ACGO - A569.单源最短路径1，由于标准版的 Bellman-Ford 算法运行效率低下，因此不保证可以通过所有的测试点）：

#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;

const int N = 1e6;

int n, m, s, dis[N];
struct Edge{
    int from, to;
    int weight;
}; vector<Edge> edges;

void bellman_ford(int origin){
    // 初始化：将所有非起点外的点都初始化为正无穷大。
    for (int i=1; i<=n; i++)
        dis[i] = 2147483647;
    dis[origin] = 0;

    // 由于图中保证不存在负环，则循环 n-1 遍即可。
    for (int i=1; i<=n-1; i++){
        for (Edge edge : edges){
            // 进行松弛操作。
            dis[edge.to] = min(dis[edge.to], dis[edge.from] + edge.weight);
        }
    }
    return ;
}

signed main(){
    // 输入输出优化。
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    // 读入题目数据并建图。
    cin >> n >> m >> s;
    for (int i=1, u, v, w; i<=m; i++){
        cin >> u >> v >> w;
        edges.push_back((Edge){u, v, w});
    }

    // 运行最短路算法。
    bellman_ford(s);

    // 输出结果，如果 dis 还是正无穷大，则证明改节点无法到达。
    for (int i=1; i<=n; i++)
        cout << (dis[i] == 2147483647 ? -1 : dis[i]) << " ";
    return 0;
}

使用 Bellman-Ford 算法判断负环的方法如下（对应例题：ACGO - A551.单源最短路径2）：

// 其他地方都不需要作改动，只改动核心松弛部分就可以了。
// 在进行第n轮松弛的时候，如果某一条边还可以松弛那么就说明这个图中存在负环。

for (int i=1; i<=n; i++){
    for (Edge edge : edges){
        // 进行松弛操作。
        if (dis[edge.from] + edge.weight < dis[edge.to]){
            // 如果在第 n 次还是可以对其进行松弛操作，那么就证明有负环。
            if (i == n){
                cout << "no solution" << endl;
                exit(0);
            }
            dis[edge.to] = dis[edge.from] + edge.weight;
        }
    }
}

因为 Bellman-Ford 算法要对每条边进行 $\lvert V\rvert - 1$ 次松弛操作，并且还需要判断一次是否存在负环，因此该算法的时间复杂度为 $O(V \times E)$，其中 $V$ 是顶点数，$E$ 是边数。Bellman-Ford 的时间复杂度相对来说比较高，因此在没有负环的时候仍然推荐使用 Dijkstra 最短路算法作为首选方案。