AcWing 853. 有边数限制的最短路（Bellman-Ford）

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 853. 有边数限制的最短路（Bellman-Ford）

作者：

张指导 , 2023-12-18 12:26:19 , 所有人可见 , 阅读 394

16

14

微信图片_20231218121536.png

76001_4f46081abb-屏幕截图-2023-03-05-143554.png

（1）什么是bellman - ford算法？

Bellman - ford 算法是求含负权图的单源最短路径的一种算法，效率较低，代码难度较小。其原理为连续进行松弛，在每次松弛时把每条边都更新一下，若在 n-1 次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。bellman - ford算法擅长解决有边数限制的最短路问题。

(通俗的来讲就是：假设 1 号点到 n 号点是可达的，每一个点同时向指向的方向出发，更新相邻的点的最短距离，通过循环 n-1 次操作，若图中不存在负环，则 1 号点一定会到达 n 号点，若图中存在负环，则在 n-1 次松弛后一定还会更新)。这里的负环指的是权值和为负的回路，而非包含负权边的回路。

实际问题：乘客从1号地点坐飞机到n号地点，求最小代价，要求换乘次数不超过k次，否则乘客心情会很差，这个k就是边数限制。

（2）bellman - ford算法的具体步骤

// 迭代n次之后的dist代表：不超过n条边的从起点开始的最短路的距离。
for n次
    for 所有边 a,b,w (松弛操作)
        dist[b] = min(dist[b],last[a] + w)

注意：
①last[] 数组是上一次迭代后 dist[] 数组的备份，由于是每个点同时向外出发，因此需要对 dist[] 数组进行备份，若不进行备份会因此发生串联效应，影响到下一个点。
②一般迭代n-1次就可以找到1 到 n 的最短路径，这里迭代 n 次是因为如果第 n 次迭代仍有更新，则说明存在权值和为负的回路（负环），迭代 n 次增加了一个求负环的功能。
③dijkstra 每次迭代可以确定一个最优边，bellman-ford 算法不可以。
④迭代了 k 次，那么就能找到：从起点开始，不超过 k 条边的，到其余所有点的最短路径。

（3）关于无穷大

在下面代码中，是否能到达n号点的判断中需要进行if(dist[n] > INF/2)判断，而并非是if(dist[n] == INF)判断，原因是INF是一个确定的值，并非真正的无穷大，会随着其他数值而受到影响，dist[n]大于某个与INF相同数量级的数即可。

（4）时间复杂度O(nm)

其中n为点数，m为边数。

（5）为何 Bellman-Ford 算法在迭代了 n-1 次后没有更新 dist 数组的话就说明不存在负权回路？

Bellman-Ford 算法是一种单源最短路径算法，它通过不断松弛边的权值来更新到各个顶点的最短路径估计值。在一般情况下，当一个图中不存在负权回路时，算法经过 n-1 次迭代就能得到所有顶点的最短路径。

如果在第 n 次迭代后仍然存在可以松弛的边，那么说明存在一个从源点出发，经过 n 条边形成的路径，这条路径上存在环路，且环路上的权值和为负数。因为每一轮迭代都是对所有边进行松弛操作，如果经过 n-1 次迭代后仍然能够松弛，说明存在一条包含 n 条边的路径，其中至少有一条边上的权值为负数。由于图中不存在权值为负数的环路，说明这条路径必然包含了一个负权回路。

因此，如果在第 n 次迭代后 dist 数组仍然发生更新，说明图中存在负权回路。在 Bellman-Ford 算法中，一般会提前退出循环，直接返回存在负权回路的信息。这是因为负权回路上的路径可以无限松弛，没有最短路径的概念，所以算法无法正常终止。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 510, M = 10010, INF = 0x3f3f3f3f; //定义常量

struct Edge{   //结构体定义边
    int a, b, c;
} edges[M];

int n, m, k;   //n个点,m条边,k次迭代
int dist[N], last[N]; //dist存储单源最短路径长度,last存储上一次迭代的值

void bellman_ford(){ //Bellman-Ford算法主函数

    memset(dist, 0x3f, sizeof dist); // dist初始化为无穷大

    dist[1] = 0; //源点路径长度设置为0

    // 迭代k次之后的dist代表：不超过k条边的从起点开始的最短路的距离
    for (int i = 0; i < k; i ++) { //k次迭代

        memcpy(last, dist, sizeof dist); //last记录本次迭代前的值

        for (int j = 0; j < m; j ++) {//枚举每条边

            Edge e = edges[j]; //取出一条边

            //松弛操作,更新dist值
            dist[e.b] = min(dist[e.b], last[e.a] + e.c);
        }
    }
}

int main()
{
    cin >> n >> m >> k;

    for (int i = 0; i < m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        edges[i] = {a, b, c};
    }

    bellman_ford();

    if (dist[n] > INF / 2) puts("impossible");
    else cout << dist[n] << endl;

    return 0;
}

详细输出版

#include <iostream>
#include <cstring>

using namespace std;

const int N = 510, M = 10010, INF = 0x3f3f3f3f;

struct Edge // 结构体定义边
{
    int a, b, w;
} e[M]; 

int n, m, k;    // n个点，m条边，k次迭代
int dist[N];   // dist存储单源最短路径长度
int last[N];    // last存储上一次迭代的值

void bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);    // dist初始化为无穷大

    dist[1] = 0;    // 源点路径长度设为0

    printf("初始状态：\n");
    for (int i = 1; i <= n; i ++)   // 枚举初始状态1到其余点的最短距离
        printf("dist[%d] = %d\n", i, dist[i]);
    puts("------------------------");

    // 迭代k次之后的dist代表：不超过k条边的从起点开始的最短路的距离
    for (int i = 1; i <= k; i ++)    // k次迭代
    {
        // last记录本次迭代前的值
        memcpy(last, dist, sizeof last);    

        for (int j = 0; j < m; j ++)    // 枚举每条边
            // 松弛操作，更新dist值
            dist[e[j].b] = min(dist[e[j].b], last[e[j].a] + e[j].w);

        printf("第%d次迭代后的结果：\n", i);
        for (int i = 1; i <= n; i ++)   // 枚举k次迭代后1到其余点的最短距离
            printf("dist[%d] = %d\n", i, dist[i]);
        puts("------------------------");
    }
}

int main()
{
    cin >> n >> m >> k;

    for (int i = 0; i < m; i ++)
        cin >> e[i].a >> e[i].b >> e[i].w;

    bellman_ford();

    if (dist[n] > INF / 2) puts("impossible");
    else cout << dist[n] << endl;

    return 0;
}

输入：

输出：

初始状态：
dist[1] = 0
dist[2] = 1061109567
dist[3] = 1061109567
dist[4] = 1061109567
dist[5] = 1061109567
------------------------
第1次迭代后的结果：
dist[1] = 0
dist[2] = 7
dist[3] = 1061109563
dist[4] = 1061109564
dist[5] = 6
------------------------
第2次迭代后的结果：
dist[1] = 0
dist[2] = 7
dist[3] = 2
dist[4] = 4
dist[5] = 6
------------------------
第3次迭代后的结果：
dist[1] = 0
dist[2] = 7
dist[3] = 2
dist[4] = 4
dist[5] = 2
------------------------
第4次迭代后的结果：
dist[1] = 0
dist[2] = 7
dist[3] = -2
dist[4] = 4
dist[5] = 2
------------------------
第5次迭代后的结果：
dist[1] = 0
dist[2] = 7
dist[3] = -2
dist[4] = 4
dist[5] = 2
------------------------
2

微信图片_20231218121047.png
n - 1次（在这里是4次）迭代后即第 n 次（在这里是第5次）迭代没有更新，说明不存在负权回路。

（6）总结

1. 为何 Bellman-Ford 算法在迭代了 n-1 次后没有更新 dist 数组的话就说明不存在负权回路？

2. B 站上不少教程都是错误的。

网上不少 Bellman-Ford 的算法都是错的，因为没使用备份数组。就比如他这个算法就是错的，没有用备份数组。他在更新边的时候发生了串联效应，导致他这个结果就都是错误的。我在群里发的实际上跑出来跟我们画的那个表格是完全一样的。

上图来自 B 站视频，下图来自算法导论，这个足够权威，我们发现算法导论上的写法用的也是备份数组更新的，与我们的写法一致。这里强烈推荐大家看 y 总在算法基础课讲的 Bellman-Ford ，很清晰、细致。

3. 各类最短路算法的总结

4. Bellman-Ford 算法的思想是贪心还是动态规划？

Bellman-Ford 算法既可以看作是一种贪心算法，也可以看作是一种动态规划算法，具体取决于不同的角度来看待算法的实现和思想。

贪心算法角度：在每一轮迭代中，Bellman-Ford 算法都会尽可能地通过对每条边进行松弛操作，不断地更新到各个顶点的最短路径估计值。这种贪心的策略是通过每一步选择当前最优的边进行松弛，直到达到最终的最短路径。在这个角度上，可以将 Bellman-Ford 算法看作是一种贪心算法。
动态规划角度： Bellman-Ford 算法的核心思想是利用子问题的最优解来构建原问题的最优解。通过不断松弛每一条边，算法逐步构建出到各个顶点的最短路径。在这个角度上，可以将 Bellman-Ford 算法看作是一种动态规划算法。

综合来说，Bellman-Ford 算法可以同时具有贪心算法和动态规划算法的特征。它通过贪心地选择边来更新最短路径，同时使用动态规划的思想构建最优解。

持续更新中......