Bellman - ford
算法是求含负权图的单源最短路径的一种算法,效率较低,代码难度较小。
其原理为连续进行松弛,在每次松弛时把每条边都更新一下,若在 n-1 次松弛后还能更新,则说明图中有负环,因此无法得出结果
算法执行流程
在松弛操作之前,需要对原本的数组进行拷贝,确保我们在松弛操作的时候,使用的是上一步松弛操作的结果,负责就会出现串联效应
为什么说存在负环可能不存在最短路径
因为belloman-ford算法
,求的是单源
的最短路径问题,那么对于负环的问题,只要负环不能到达终点,那么负环其实是对结果没有影响的。因为从起点到终点,已经确定了最多走k条
边
但如果负环可以到达终点,那么任由负环一直循环下去,一定会把最短路径变为 -INF
Belloman-ford算法判断负环的方式
我们一共有n个点
,那么对于一个点来说,我最多松弛n-1
次就可以找到一个最短路径,那么当我们继续第n次
松弛的时候,如果还可以进行松弛,那就说明存在负权的回路
判断路径是否可达
/2
的原因是,0x3f3f3f3f
是一个确定的值,并非真正的无穷大,会随着其他数值而受到影响,dist[n]
大于某个与0x3f3f3f3f
相同数量级的数即可。
另外,根据题目的数据范围,负权边最多可以影响500 * 10000
次,但是0x3f3f3f3f
远远大于这个数,所以说以此来判断是否存在最短路
源程序
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510, M = 1e4 + 10;
int n,m,k; // n个点,m条边,k 最多经过k条边
int dist[N], backup[N]; // dist[i] 从1->i 的最短距离,backup dist的一个副本
struct edges{
int u,v,w;
}e[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 i = 0; i < m; i++) {
int u = e[i].u, v = e[i].v, w = e[i].w;
dist[v] = min(dist[v], backup[u] + w);
}
}
if(dist[n] >= 0x3f3f3f3f / 2) return -1;
return dist[n];
}
int main() {
cin >> n >> m >> k;
for(int i = 0; i < m; i++) {
cin >> e[i].u >> e[i].v >> e[i].w;
}
int t = bellman_ford();
if(t == -1) puts("impossible");
else cout << t << endl;
return 0;
}