Bellman-ford算法详解

什么是Bellman-ford算法

贝尔曼-福特算法（Bellman-Ford）是由理查德·贝尔曼（Richard Bellman）和莱斯特·福特创立的，求解单源最短路径问题的一种算法。其优于Dijkstra的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高。但它也有特别的用处，一般用于实现通过m次迭代求出从起点到终点不超过m条边构成的最短路径。

Dijkstra算法不能解决带有负权边的问题，而Bellman-ford算法可以解决带有负权边的问题，是求解带负权边的单源最短路问题的经典算法。时间复杂度是O(nm)，核心思想是”松弛操作”。解决带负权边的单源最短路问题还有一个常用的算法是SPFA算法，SPFA算法的时间复杂度一般是O(m)，最坏是O(nm)。

总结一下就是Dijkstra算法可以解决不带负权边的问题，而对于带有负权边的问题，又有Bellman-ford算法和SPFA解决。

基本思路

首先n次迭代，每一次循环所有边。我们这里用a,b,w表示存在一条从a走到b的边，权重是w。这里存边方式有很多种，可以用邻接表，结构体等。遍历所有边的时候更新一下其他点的距离，和Dijkstra算法类似，用当前这个点更新和它相连的点距离起点的距离。我们这里用dist数组表示每个点到起点的距离，那么更新操作就是dist[b]=min(dist[b],dist[a]+w)，这样就可以更新和a相连的b点距离起点的距离，这个更新的过程就是”松弛操作”。忘了说的一点就是在循环所有边的时候，每一次循环要先把dist数组备份一下，防止串联，这个后面会说。循环n次之后对所有的边一定满足dist[b]<=dist[a]+w，这个叫”三角不等式”。

这个就是Bellman-ford算法的基本思路。

但是注意如果图中有负权回路的话，最短路就不一定存在了

举个栗子

我们看这个图，红色的数字表示边的权重，我们想求一下1号点到5号点的最短路径，我们从1走到2，2,3,4号点围成了一个圈，圈的总权重是5+-4+-2=-1，那么转一圈长度就会减一，因此我们可以转无穷多圈，转无穷多圈总长度就会变成负无穷，出圈的话还是负无穷。所以说图中存在负权回路的话，从1号点到n号点的距离就会变成负无穷，就不存在了。

所以能求出来最短路的话，图中是没有负权回路的。

而Bellman-ford算法是可以判断图中存不存在负权回路。首先上面的迭代次数是有实际意义的，比如我们迭代了k次，那么我们求的最短距离就是从1号点经过不超过k条边走到n号点的最短距离。所以在第n次迭代的时候又更新了某些边的话，就说明路径中一定存在环，并且是负权回路。因为第n次迭代在不存在负权回路的情况下是遍历到第n号点了，后面是没有点了，如果还能更新，说明路径中存在回路，而且是负权回路。

但是一般找负环是不用Bellman-ford算法，一般是用SPFA算法，这里我们只要知道Bellman-ford算法可以找负权回路即可。

总结

Bellman-ford算法的思路也很简单，直接就是两层循环，内层循环所有边，外层循环就是循环所有边的次数，这个外层循环次数一般是题目控制的。时间复杂度是O(n*m)

案例

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从 1 号点到 nn 号点的最多经过 kk 条边的最短距离，如果无法从 1 号点走到 n 号点，输出

impossible

。

注意：图中可能 存在负权回路 。

输入格式

第一行包含三个整数 n,m,k。

接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x到点 y 的有向边，边长为 z。

点的编号为 1∼n。

输出格式

输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。

如果不存在满足条件的路径，则输出

impossible

。

数据范围

1≤n,k≤500
1≤m≤10000
1≤x,y≤n
任意边长的绝对值不超过 10000。

输入样例：

3 3 1
1 2 1
2 3 1
1 3 3

输出样例：

3

思路

这里要注意的就是我们用结构体去存边的信息，还有一个就是backup数组，这个数组是给dist数组备份的数组。我们在循环所有边的操作中，在每一次循环之前要先把上一次循环后的dist数组备份一下。防止**"串联"**，什么是串联呢？

举个栗子

我们以样例为例

样例是这样一张图，k是1，也就是要求从1号点出发到3号点最多经过1条边的最短距离，通过图很容易就可以看出，最短距离就是3，也就是1号点直接到3号点的距离。

这里我们已经知道最短距离是3了，如果我们不把上一次循环后的dist备份的话会出现什么后果呢？我们根据Bellman-ford算法的步骤，也就是两层循环，外层循环题目控制的是k，也就是1，内层循环所有的边。也就说只会进行一次迭代。我们看一下内层循环的过程，首先一共有三条边，所以内层循环要循环三次。我们看一下内层循环后的结果。注意：这里是没有备份dist数组的结果

1号点

2号点

3号点

内层循环第一次执行

0

∞

∞

内层循环第二次执行

0

1

∞

内层循环第三次执行

0

1

2

可以发现，如果我们没有备份上一次的dist数组的话，最短距离变成了2。内层循环只迭代了一次，但是在更新的过程中会发生”串联”。比如说先更新了2号点，然后我们用2号点更新了3号点距离起点的距离，这样就发生了”串联”，，3号点不能被2号点更新，这样就不满足题目要求了，因为题目要求最多不经过1条边，上面我们说了，迭代次数是有实际意义的，我们迭代1次，那我们求的最短距离就是最多不经过1条边的最短距离。

怎么保证不发生串联呢？我们保证更新的时候只用上一次循环的结果就行。所以我们先备份一下。备份之后backup数组存的就是上一次循环的结果，我们用上一次循环的结果来更新距离。所以我们这样写dist[b]=min(dist[b],backup[a]+w)来更新距离，而不是dist[b]=min(dist[b],dist[a]+w)，这样写就会发生上面说的”串联”现象。

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=510,M=1e4+10;
int dist[N],backup[N];
int n,m,k;
//这里用结构体存边的信息
struct node
{
    int a,b,c;
}edg[M];
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<m;j++)
        {
            int a=edg[j].a,b=edg[j].b,c=edg[j].c;
            dist[b]=min(dist[b],backup[a]+c);
        }
    }
    return dist[n];
}
int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        edg[i]={a,b,c};
    }
    //这里不用0x3f3f3f3f是因为防止n号点被负权边更新
    if(bellman_ford()>0x3f3f3f3f/2)
    cout<<"impossible";
    else
    cout<<dist[n];
    return 0;
}