思路
bellman_ford算法可以处理负权图或者有边数限制的最短路问题,Dijkstra算法无法处理
- 创建dist数组,初始化为无穷大,表示每个点到起点的距离。原点的距离当然为零
- 外层循环:迭代n次,这个n其实就是最短路径的长度。
- 内层循环:遍历图中的每条边,对每条边进行一次松弛操作
- 如果第n次迭代,仍然可以进行松弛操作,就说明有至少长度为n+1的最短路径。又因为图中只有n个点,由抽屉原理可知,路径中至少存在两个相同的点,说明图中存在负权回路。
- 备份数组的意义在于,在一次遍历中,每次松弛操作后更新的dist数组的结果会影响下次的松弛操作,因此利用backup数组备份上次迭代后的dist数组。
代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,k;
const int N=10010;
struct Edge{
int a,b,c;
}edge[N];
int dist[N],backup[N]; //备份数组
int bellman_ford(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
//根据题意,k条边限制,因此我们进行k次迭代
for(int i = 0;i<k;i++){
//备份上次迭代的dist数组,避免串联,找到非k条边的最短路。
memcpy(backup,dist,sizeof dist);
for(int j=1;j<=m;j++){
int a=edge[j].a,b=edge[j].b,w=edge[j].c;
//进行松弛操作,类似三角形不等式。
//注意这里比较就要用backup比较
if(dist[b]>backup[a]+w){
dist[b] = backup[a] + w;
}
}
}
//因为存在负权,可能将dist[n]更新即减小,但又非最短距离
if(dist[n]>0x3f3f3f3f/2) return -1;
else 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};
}
if(bellman_ford()==-1)
printf("impossible\n");
else printf("%d",bellman_ford());
return 0;
}