- 认为讲得好不妨支持一下
Bellman-Ford算法
- 是一种单源最短路算法
- 常用于解有边数限制的最短路(边权可为负数)
- 时间复杂度 $O(nm)$
1 - 思路
所有的单源最短路算法的基本思路只有一个,
那就是: 拓展更新 , $Bellman-Ford$ 便是其中的经典算法。
步骤
-
预处理,除出发点到自身的最短距离为0以外,到其他点的最短距离都为无穷大;
-
输入,加边,建图,并声明一个数组 $backup$ ,表示上一轮更新时求出的每个点的最短路;
-
将 $backup$ 与 $dist$ 同步,原因是这一轮 $dist$ 的更新开始了;
-
更新所有边指向的点的最短路;
-
重复上述3,4两步,直到达到边数要求。
原理
- 注: $backup$ 是边数为 $k-1$ 时的每个点的最短路。
2 - 代码
例题:
有边数限制的最短路
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510, M = 100010, INF = 0x3f3f3f3f;
int n, m, k;
int dist[N], backup[N];
//dist[i]表示第i个点边数为k的最短路长度
//backup[i]表示第i个点边数为k-1的最短路长度
struct Edge
{
int u, v, w;
} edges[M]; //使用结构体存边,多个边构成一幅图
//Bellman-Ford主体
int Ford()
{
dist[1] = 0; //出发点到自身的距离为0
for (int i = 1; i <= k; i ++)
{
memcpy(backup, dist, sizeof(dist)); //将第k-1轮更新完成的dist拷贝到backup
for (int j = 1; j <= m; j ++) //枚举每一条边
{
int a = edges[j].u, b = edges[j].v, c = edges[j].w; //始点、终点、边权
dist[b] = min(dist[b], backup[a] + c); //更新
}
}
return dist[n];
}
int main()
{
memset(dist, 0x3f, sizeof(dist)); //方便在第一次对点更新时用min函数
scanf("%d%d%d", &n, &m, &k);
//加边
for (int i = 1; i <= m; i ++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
edges[i] = {u, v, w};
}
int res = Ford();
if (res >= INF / 2) puts("impossible");
//即使不连通,点n也可能被更新(负权边),值可能会减小
else printf("%d\n", res);
return 0;
}