Bellman-Ford 算法¶
Ballman-Ford 算法是一种基于松弛操作来求单源最短路的的算法，可以求出有复权的图，并且可以判断从源点开始能否可以到达一个负环。
什么是松弛操作¶
假设 \(d(x)\) 表示为源点到 \(x\) 的最短路径长度，那么很显然若源点为 \(1\)，那么 \(d(1)=0\)。现在我们找到了一条边 \((u,v)\)，那么 \(d(v)=\min(d(v),d(u)+w(u,v))\)。因为我们把 \(1-u\) 的路径眼神到了 \(1-v\)，那么值自然就需要加上 \(w(u,v)\)，但是这不一定是最短的，因此我们需要取最小值。
为什么呢？接下来我介绍一个十分脑残的定理：假设 \(u\) 到 \(v\) 的最短路径经过的点的序列为 \(a\)，那么对于 \(a\) 的任意一个子串 \(b\)，\(b_1\) 到 \(b_{\mid b\mid}\) 的路径也必定是最优的。因此，我们知道了一条最短路径是可以由两条同样最短的路径给拼起来的。
算法思想¶
Bellman-Ford 做的其实就是不断地进行松弛操作。我们知道，一条最短路经过的边的数量最多为 \(n-1\)，而松弛操作每一次能够给最短路径多贡献一条边，那么我们就需要枚举 \(n-1\) 次松弛操作，然后枚举所有的边，进行松弛操作。经过了 \(n-1\) 次松弛操作之后，源点到任意结点的最短路经就找到了。
算法时间复杂度为 \(\mathcal O(nm)\)，但是在松弛过程中如果已经没有可以松弛的点了，我们就退出松弛操作，进行一点点时间上的优化。
代码
vector<int> bellmanFord(int s) {
vector<int> d(n + 1, 1e9);
d[s] = 0;
for (int i = 1; i < n; i++) {
for (int j = 1; j <= m; j++) {
d[v[i]] = min(d[v[j]], d[u[j]] + w[j]);
}
}
return d;
}
判断负环¶
我们知道，当最短路经过了一个负环，他就会一直绕在哪里，因为边权是负的，一直转就可以获得更优的答案。在 Bellman-Ford 中，如果经过了 \(n-1\) 次松弛操作之后还可以进行松弛，那么就说明从源点开始能够到达一个负环。
代码
vector<int> bellmanFord(int s) {
vector<int> d(n + 1, 1e9);
d[s] = 0;
for (int i = 1; i < n; i++) {
for (int j = 1; j <= m; j++) {
d[v[i]] = min(d[v[j]], d[u[j]] + w[j]);
}
}
for (int i = 1; i <= m; i++) {
if (d[u[j]] + w[i] < d[v[i]]) {
return {-1};
}
}
return d;
}
队列优化（SPFA）¶
在大多数情况下我们并不需要那么多的松弛操作，因此我们可以选择使用一个队列用来记录那些点需要进行松弛操作。观察代码，很显然，之后被松弛的结点所连接的邻点才需要再次进行松弛操作，因此代码就很显然了。
最优情况下每一个点只松弛一次，时间复杂度是 \(\mathcal O(n+m)\) 的，但是最坏情况下直接跟 Bellman-Ford 到了 \(\mathcal O(nm)\)，这也就是为什么能用 Dijkstra 就尽量不用 SPFA 的原因。尽管大家为 SPFA 提出了许多其他的优化，但是还是可以被毒瘤出题人给卡，有些优化甚至可以达到指数级！因此使用 SPFA 的时候一定需要看清楚数据范围。
注意 SPFA 不想 Bellman-Ford 限制了松弛次数，如果遇到了负环还是会死循环的，因此我们需要使用一个数组来记录入队次数，如果入队次数超过了 \(n\)，那么就说明找到了负环。
特别注意
如果出现了重边，那么松弛操作数量可能超过 \(n-1\)，这是我们就需要判断入队次数而不是松弛次数，不然可能会被 Hack。这也是一个高频易错点。
有的人活着，他已经死了。——臧克家
代码
bool spfa(int s) {
fill(d + 1, d + n + 1, 1e9);
fill(f + 1, f + n + 1, 0);
fill(s + 1, s + n + 1, 0);
for (q.push(s), d[s] = 0, f[s] = 1; q.size(); q.pop()) {
int t = q.front();
for (int i : e[t]) {
if (d[t] + i.v < d[i]) {
d[i] = d[t] + i.v;
if (!f[i]) {
if (++s[i] >= n) {
return 1;
}
q.push(i);
f[i] = 1;
}
}
}
}
return 0;
}