bellman_ford算法模板题题解&学习笔记
1 学习笔记
1.1 算法介绍
bellman_ford算法是一种单源最短路算法,并且可以判断负环,而且用的是暴力写法。
1.2 算法流程
一下是bellman_ford算法的算法流程:
那么按照上面的描述,这副图变成了这样,并继续操作:
但是在这个算法中,并不是更新一遍就能完成的,上面举得例子只是巧合,实际上要执行上面的操作n遍才能保证答案正确。
以下是bellman_ford算法的核心代码:
for(int i=0;i<n;i++)//循环n次
{
for(int i=0;i<m;i++)
{
int a=v[i].a,b=v[i].b,w=v[i].w;//v数组存的是每条边
dist[b]=min(dist[b],dist[a]+w);//dist表示目前这个点的最小点权
}
}
而下面要来讲bellman_ford算法的应用题(与模板题有些不一样)
2. 模板题题解
首先,我们只需要循环k次枚举边操作就行了,因为更新k次边就是k段路程
可能有人会问,如果边里面保存的是1->2 2->3 3->4 … 这样,不是大于k的话也能得出答案吗?
所以我们需要一个数组bakcup,bakcup用来保存上一次更新每个点的点权,这样的话,假设第一次只更新了点1,然后更新点2
点2更新完后遍历像刚刚说的那种结构的边的时候因为前一次的时候点2还未被更新,所以只能等到下一次遍历才会更新点3
那么,按照以上思路,便可写出题解;
#include <bits/stdc++.h>
using namespace std;
int n,m,k;
struct node
{
int a,b,w;
};
vector<node> v;
int dist[100010],bakcup[100010];
int bellman_ford()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=0;i<k;i++)
{
memcpy(bakcup,dist,sizeof dist);
for(int i=0;i<m;i++)
{
int a=v[i].a,b=v[i].b,w=v[i].w;
dist[b]=min(dist[b],bakcup[a]+w);//更新
}
}
if(dist[n]>0x3f3f3f3f/2) return 0x3f3f3f3f;//因为像y总在上课说的,如果当前点是无限但是边权却是负数,他是可以更新相邻没有被更新甚至已经被更新的点的,所以要/2特判掉这种情况
return dist[n];
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
v.push_back({x,y,z});
}
int t=bellman_ford();
if(t==0x3f3f3f3f) printf("impossible");
else printf("%d",t);
}
希望大家喜欢,同时有什么说的不对的欢迎指出来