Bellman-Ford算法详解：单源最短路径的计算方法
Bellman-Ford算法详解：单源最短路径的计算方法
Bellman-Ford算法是一种用于计算单源最短路径的算法，特别适用于包含负权边的图。与Dijkstra算法相比，Bellman-Ford算法虽然效率较低，但其适用范围更广，能够处理负权边的情况，并且可以检测图中是否存在负权回路。本文将详细介绍Bellman-Ford算法的性质、基本思路以及如何处理有边数限制的最短路径问题。
一、性质
- 适用性：适用于含有负权边的图（Dijkstra不适用）
- 效率：更简单，但效率慢
- 负权回路检测：如果对应路径存在负权回路则没有最短路径（可用于判断图中是否存在负权回路）
- 边数限制：相比于SPFA，若最短路径有边数限制则只能使用Bellman-Ford
负权回路：图中带环且环中所有边的权重和为负。
二、思路
Bellman-Ford算法的思路十分简单粗暴。与Dijkstra算法类似，我们用一个dist数组存放源节点到任意节点的最短路径。
首先，在求最短路径前，我们需要将源节点到自己的距离初始化为0，到其他节点的距离初始化为最大值。
然后，我们遍历所有的边。对于一条边，我们这里可以直接用一个结构体存储其信息，例如：
struct edge{
int a, b, w;
}edges[M];
其中a为有向边出发的节点，b为有向边指向的节点，w为边的权重。
遍历所有的边，如果dist[a]+w < dist[b]，则更新最短路径。
以同样的方式一共循环n次，我们就能得到源节点到任意节点的最短路径。
有时不一定非要循环n次才能得到最优解，例如上面我们只循环了3次。但最坏的情况下，如果我们的图是这样的呢？
有n个节点，但只有n-1条边，我们至少循环n-1次才能将所有节点更新。
那我们不能只循环n-1次吗？
前面提到，Bellman-Ford算法可用于检测图中是否存在负权回路，具体是如何检测的？靠的就是这多出来的一次循环。
首先解释一下为何路径中存在负权回路则不存在最短路径，因为我们如果在这个负权回路中一直走，那么路径长度不就一直在变小直到负无穷吗？
可以看到，在上面最坏的情况下，我们也只需要循环n-1次就能将源节点到每个节点的最短路径求出来，而最后一次循环中不会有节点被更新。但如果存在负权回路，则最后一次循环中一定还会有节点被更新。通过判断我们就可以知道图中是否存在负权回路。
即使每次遍历边的顺序不同也不会影响最后的结果，但每次循环中dist数组中的值可能不同。因为如果遍历边的顺序与边的指向一致，我们可以连续更新多个节点，例如：
可以看到dist的数组更新是串联的，即一个位置更新可能影响到其他位置，如果我们没有对最短路径的边数进行限制的话就无需多虑，但如果最短路径有边数限制，那我们就需要一个额外的备份数组来辅助节点更新。
三、有边数限制的最短路径
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510, M = 10010;
struct edge{
int a, b, w;
}edges[M];
int n, m, k;
int dist[N], backup[N];
//最短路径有边数限制，所以我们还需要一个备份数组
int bellman_ford()
{
//初始化dist数组
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
//最短路径不能超过k条边，因此我们循环k次
for(int i = 0;i < k;i++)
{
//将上一次循环中dist数组的结果存入backup数组
memcpy(backup, dist, sizeof dist);
for(int j = 0;j < m;j++)
{
int a, b, w;
a = edges[j].a, b = edges[j].b, w = edges[j].w;
dist[b] = min(dist[b], backup[a] + w); //用backup数组来更新dist数组
}
}
return dist[n];
}
int main()
{
cin >> n >> m >> k;
for(int i = 0;i < m;i++)
{
int a, b, w;
cin >> a >> b >> w;
edges[i] = {a,b,w}; //存边
}
int ans = bellman_ford(); //Bellman-Ford算法
if(ans > 0x3f3f3f3f / 2) cout << "impossible";
//返回值过大不符合预期，可以判断不存在满足条件的路径
else cout << ans;
return 0;
}