最短路算法之：SPFA 算法

· · 算法·理论

最短路系列：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，就讲到这里。

再见！