算法基础班–第三章–5.3最短路—Bellman-Ford算法(有边数限制的最短路)
算法模板
//时间复杂度O(n*m)
//注意在模板题中需要对下面的模板稍作修改,加上备份数组,详情见模板题
int n, m;
int dist[N]; // dist[x]存储1到x的最短路距离
struct Edge{//用结构体存所有边
int a, b, w; //边a表示出点, 边b表示入点,w表示边的权重
} edges[M];
//求1到n的最短距离,如果无法从1走到n,则返回-1
int bellman_fort() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
//如果第n次迭代仍然会松弛三角不等式,就说明存在一条长度是n+1的最短路径,由抽屉原理,路径中至少存在两个相同的点,说明图中存在负权回路
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
if (dist[b] > dist[a] + w)
dist[b] = dist[a] + w;
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1;
else return dist[n];
}
本题对应的模板
int dist[N], backup[N];
struct Edge{//用结构体存所有边
int a, b, w;
} edges[M];
int bellman_fort() {
memset(dist, 0x3f, sizeof dist);//初始化
dist[1] = 0;
for (int i = 0; i < k; i++) {
memcpy(backup, dist, sizeof dist);//每次在进行新的迭代之前,需先把dist[]备份
for (int j = 0; j < m; j++) {
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
dist[b] = min(dist[b], backup[a] + w);//使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1; //这里是因有负权边,可能dist[n]<0x3f3f3f (具体见笔记本)
else return dist[n];
}
时间复杂度 O(n*m)
本题完整代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510, M = 10010;
int n, m, k;
int dist[N], backup[N];
struct Edge{//用结构体存所有边
int a, b, w;
} edges[M];
int bellman_fort() {
memset(dist, 0x3f, sizeof dist);//初始化
dist[1] = 0;
for (int i = 0; i < k; i++) {
memcpy(backup, dist, sizeof dist);//每次在进行新的迭代之前,需先把dist[]备份
for (int j = 0; j < m; j++) {
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
dist[b] = min(dist[b], backup[a] + w);//使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1; //这里是因有负权边,可能dist[n]<0x3f3f3f (具体见笔记本)
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);
edges[i] = {a, b, w};
}
int t = bellman_fort();
if (t == -1) puts("impossible");
else printf("%d\n", t);
return 0;
}