最短路系列：SPFA 算法
大家好，我是Weekoder！
终于，我们的最短路算法 SPFA 闪亮登场了！
虽然话是这么说，但是我还是建议大家先学习 Dijkstra 算法，再来学习 SPFA。
并且我们在这里学习的 SPFA 算法只能通过P3371，并不能通过标准版的P4779。
SPFA 的原型——Bellman-Ford
在学习 SPFA 之前，我们要先学习他的原型 Bellman-Ford。其实 Bellman-Ford 都不能说是 SPFA 的原型，SPFA 其实就是 Bellman-Ford，他们是同一个东西。Bellman-Ford 与 Dijkstra 不同，是以边为研究对象的最短路算法。他的思想是这样的：图中有 \(m\) 条边，对于一共 \(n-1\) 次除了起点外其他点的松弛，每一次可以枚举所有 \(m\) 条边。对于当前枚举的边 \(u\to v\)，我们可以试图让 \(u\) 松弛 \(v\)，也就是松弛这条边。每次枚举 \(m\) 条边，就必定有至少一个点被松弛。与此往复 \(n-1\) 次，就得到了最短路。代码可以说非常短，比 floyd 还好理解。
\(\text{Code:}\)
void bellman_ford() {
for (int i = 1; i <= n; i++)
dis[i] = 2147483647;
dis[s] = 0;
for (int i = 1; i < n; i++)
for (int j = 1; j <= m; j++)
if (dis[e[j].v] > dis[e[j].u] + e[j].w)
dis[e[j].v] = dis[e[j].u] + e[j].w;
}
还可以注意到，Bellman-Ford 因为是以边为研究对象的，所以是以类似于最小生成树中的存储方式存储边的。
可以看到 Bellman-Ford 的时间复杂度为 \(\Theta(nm)\)。
但是很可惜，这份代码仅能获得 \(70\text{pts}\)。
\(\color{#52C41A}\texttt{7 AC }\color{#052242}\texttt{ 3 TLE}\)
这时候我们就要来优化我们的代码了。
Bellman-Ford 的队列优化——SPFA
是不是感觉绕了一圈又回来了。
确实，Bellman-Ford 的队列优化就是 SPFA。但在国外，人们只会叫他 Bellman-Ford 的队列优化，而只有中国的 OIer 才会喜欢叫 SPFA，因为这个优化并没有改变时间复杂度的上限，最坏的时候仍然会达到 \(\Theta(nm)\)。那么具体是怎么用队列优化呢？
实际上我们注意到，只有被松弛过的点才能继续松弛别的点，那我们就可以利用这一性质进行优化。那我们就可以把松弛过的点放进一个容器里，拿出来的时候再去松弛别的点。拥有这样先进先出特点的容器，没错，就是队列了。这样，就可以减少无意义的枚举，优化时间复杂度。
我们用一个 \(vis\) 数组来标记某个点是否在队列中。
\(\text{Optimal Code:}\)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 5, M = 5e5 + 5;
struct Edge {
ll to, w;
};
ll n, m, s, dis[N];
bool vis[N];
vector<Edge> nbr[N];
void bellman_ford() {
queue<int> q;
for (int i = 1; i <= n; i++)
dis[i] = 2147483647;
dis[s] = 0;
q.push(s);
vis[s] = 1;
while (!q.empty()) {
int cur = q.front(); q.pop();
vis[cur] = 0;
for (auto nxt : nbr[cur]) {
int to = nxt.to, w = nxt.w;
if (dis[to] > dis[cur] + w) {
dis[to] = dis[cur] + w;
if (!vis[to]) {
q.push(to);
vis[to] = 1;
}
}
}
}
}
int main() {
cin >> n >> m >> s;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
nbr[u].emplace_back((Edge){v, w});
}
bellman_ford();
for (int i = 1; i <= n; i++)
cout << dis[i] << " ";
return 0;
}
长的很像 BFS，但是会取消标记。注意 \(vis\) 的意义。
小结
SPFA 最短路算法就这样讲完了。他可以处理负权图，只要图随机，跑的还是很快的。在图中有负权的情况下，必须使用 SPFA 来保证正确性。那么关于 SPFA，就讲到这里。