数据结构与算法学习笔记----Bellman-ford算法

数据结构与算法学习笔记----Bellman-ford算法

@@ author: 明月清了个风
@@ first publish time: 2024.12.18

Bellman-ford算法

这是一种单源最短路径算法，适用于图中存在负权边的情况。

基本思想

通过逐步松弛更新最短路径。

在每一轮迭代中，检查所有边，如果从某一节点出发可以得到更短的路径，那么就进行更新，算法的特点是可以计算最多经过k条边的最短路径，也可以用于检测负环，不过时间复杂度较高。

算法流程

1. 初始化：设定源点st到每个节点的距离为无穷大，源点到自身距离为$0$。
2. 循环$k$次，每次都进行松弛操作，遍历所有边，并更新，对于每一条边$(a,b,w)$，如果通过节点$a$到节点$b$的路径比已知的源点到节点$b$的最短路径更短dist[b] > dist[a] +w,那么就对节点$b$的最短路径进行更新。
3. 负环检测：循环$k+1$次时仍有边的长度被更新，那么说明存在负环。

时间复杂度为$O(V\times E)$，$V$是节点数，$E$是边数。

经过最多$k$条边正确性证明

使用数学归纳法进行证明：

1. 首先是$k=0$的情况

   在第$0$轮迭代的过程中，只有源点st的距离为$0$，源点到源点经过$0$条边，因此正确。

2. 假设经过$k$轮后，源点出发到各节点的最短路径包含最多$k$条边式正确的。

   那么在第$k+1$轮松弛时，假设有一条边$(u,v)$，更新了到节点$v$的最短路径为dist[v] = dist[u] + w ,由于在第$k$轮中保证了源点出发到各节点的最短路径最多包含了$k$条边，因此源点到点$u$的最短路径最多包含了$k$条边，所以在这一轮对节点$v$的更新使源点到节点$v$的最短路径变成了最多包含$k+1$条边，因此算法正确。

负权回路检测正确性证明

对于一个有$V$个节点的图来说，两点之间的边数不可能超过$V-1$。

由于两点之间存在负权回路，导致可以无限循环更新，每次都会使最短路径更短。因此对于Bellman-Ford算法来说，进行了$V-1$次循环后，在第$V$轮循环中，还能有一条边$(u,v)$被更新了，那就说明，他们之间存在负权回路，也就是只要在第$V$轮中存在dist[u] + w < dist[v]，就证明存在负权回路。

注意点

1. 串联问题：因为每一轮循环中都会对所有边进行松弛操作，假设有一张图如图所示，在第一轮遍历中，首先遍历到边$(a,b)$，更新$dist[b]=1$，然后遍历到边$(b,c)$，更新$dist[c]=dist[b]+1=2$，这就造成了只松弛了一轮却使点$c$的最短路径中出现了两条边，因此需要进行备份操作，遍历到边$(b,c)$的正确情况应该是$dist[c]=last[b]+1$，使用点$b$上一轮中的结果。
   

2. 路径不存在的判断：在之前Dijkstra中，对于终点无法到达的情况，直接判断dist[n] ==inf即可，但是在bellman-ford算法中，因为负权边的存在，可能会在遍历所有边的时候出现，某个同样无法到达的点$v$到$n$的距离为负数，这样就会满足$dist[n]>dist[v]+w$，从而将点$n$的距离更新了，此时dist[n] < inf，因此不能直接用原来的条件判断，只要判断大于一个大数即可。

Acwing 853. 有边数限制的最短路

[原题链接](853. 有边数限制的最短路 - AcWing题库)

给定一个$n$个点$m$条边的有向图，图中可能存在重边和自环，边权可能为负数。

请你求出$1$号点到$k$号点的最多经过$k$条边的最短距离，如果无法从$1$号点走到$n$号点，则输出$impossible$。

注意：图中可能出现负权回路。

输入格式

第一行包含三个整数$n$,$m$,$k$。

接下来$m$行，每行包含三个整数$x$、$y$、$z$，表示存在一条从点$x$到点$y$的有向边，边长为$z$。

输出格式

输出一个整数，表示$1$号点到$n$号点的最多经过$k$条边的最短距离。

如果无法从$1$号点走到$n$号点，则输出$impossible$。

数据范围

$1\le n,k\le 500$,

$1\le m\le 10000$,

$1\le x,y\le n$,

图中涉及边长均不超过10000。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 10010, M = 510, inf = 0x3f3f3f3f;struct Edge
{int a, b, c;
}edge[N];int n, m, k;
int dist[M];
int last[M];void bellman_ford()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;for(int i = 0; i < k; i ++){memcpy(last, dist, sizeof dist);for(int j = 0; j < m; j ++){int a = edge[j].a, b = edge[j].b, c = edge[j].c;dist[b] = min(dist[b], last[a] + c);}}
}int main()
{cin >> n >> m >> k;for(int i = 0; i < m; i ++){int a, b, c;cin >> a >> b >> c;edge[i] = {a, b, c};}bellman_ford();if(dist[n] > inf / 2) puts("impossible");else cout << dist[n] << endl;return 0;
}