Bellman-Ford算法
可以求出是否存在负权边的问题但时间复杂度较高
算法过程
更新过程叫:松弛操作
for loop n 次
备份一下//因为边数有限制,可能更新后的边数太长不能用
for 所有边a,b,w(a->b的边权值为w)
更新所有边dist[b]=min(dist[b],dist[a]+w;
//看看当前点通过a到b的距离和直接到b的距离哪个短
循环n次后一定满足dist[b]<=dist[a]+w;//三角不等式
某些题只能用Bellman-Ford算法
比如:输出一个整数,表示从1号点到n号点的最多经过k条边的最短距离。
算法1
基本按照y总讲的过程就能实现,比起之前的Dijkstra简单的多,甚至可以直接定义一个结构体进行操作。
主要核心在于以下几条语句:
memset(dist,0x3f,sizeof dist);dist[1]=0;
初始化,不难,但容易遗忘
memcpy(backup,dist,sizeof dist);
防止串联,所以要进行一个备份,因为不知道能不能用这个长度的距离更新。有点类似于计网里面的慢收敛。
for(int j=0;j<m;j++)
{
int a=edge[j].a,b=edge[j].b,w=edge[j].w;
dist[b]=min(dist[b],backup[a]+w);
}
最关键的更新语句,也类似于Dijkstra里面的更新,主要记住有几条边更新几次,但是是利用backup里面的内容更新的,因为最多就能走k条边。
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510,M=1e5+10;
int n,m,k;
int dist[N],backup[N];
struct Edge
{
int a,b,w;
}edge[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=edge[j].a,b=edge[j].b,w=edge[j].w;
dist[b]=min(dist[b],backup[a]+w);
}
}
if(dist[n]>0x3f3f3f3f/2) return -1;
return dist[n];
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<m;i++)
{
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
edge[i]={a,b,w};
}
int t=bellman_ford();
if(t==-1)puts("impossible");
else cout<<t<<endl;
return 0;
}