[编程笔记]-Bellman-Ford

用处

常用于在有负权边的有向无环图中进行最短路判断。

要是有负权回路就没有结果了（或结果是负无穷）。解释：每转一圈距离就减一点，那我转啊转啊转啊转啊……然后就不出来了(～￣▽￣)～

事实上用死了的SPFA更好o(￣︶￣)o

因此，事实上，一般用BELLMAN-FORD的都是有边数长度限制的题目，具体会在世纪意义中说明。

实现

操作

重复执行n次：
遍历所有边，尝试更新每个边指向点的dis。（松弛操作）

啊对了每次遍历记得用上一次操作的结果来操作，不然会发生串联（本来要走两步的，但因为先后遍历了相邻两条边，导致一步之内走了两步）
。

。

对就没了(^▽^)

实际意义

迭代第k次，dis里存的是经过不超过k条边能到达的最短距离。

因此，可以求有最大边数限制的最短路问题，并且有负环也无所谓。

同时，它还可以判断是否存在负环：

若迭代第n次，还有点被更新，说明图中存在一条长度大于等于n的边，但一共只有n个点，所以一定有至少两个点被走了两次，所以存在环。又因为可以更新，所以这个环是负环。

然鹅一般找负环都是用SPFA做hh

例题

由于负权最短路一般都给SPFA实现去了，这就来一道只能用贝尔曼弗德的题吧。

AcWing853-有边数限制的最短路

#include<bits/stdc++.h>
using namespace std;

const int N=505,M=1e4+5;

struct edge{
    int x,y,z;
}es[M];

int n,k,m;
int dis[N],lis[N];

void bellman_ford(){
    for(int t=0;t<k;t++){
        for(int i=1;i<=n;i++)lis[i]=dis[i];//记录上一次的结果防止串联
        for(int i=1;i<=m;i++){
            dis[es[i].y]=min(dis[es[i].y],lis[es[i].x]+es[i].z);
        }
    }
    if(dis[n]>0x3f3f3f3f/2)cout<<"impossible";//不能写等于正无穷，因为负权边两侧正无穷能更新对方
    else cout<<dis[n];
}

int main(){
    cin>>n>>m>>k;
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=m;i++){
        cin>>es[i].x>>es[i].y>>es[i].z;
    }
    dis[1]=0;
    bellman_ford();
    return 0;
}

完结撒花o(￣︶￣)o