spfa

1 算法背景与直觉

前置算法: bellman-ford。

在 Bellman-Ford 算法中，我们每一轮都对图上的所有边进行松弛操作。

回顾松弛操作的定义：

思考一个问题：什么样的边才可能成功进行松弛？

如果点 $u$ 的最短路估计值 $dis(u)$ 自上一轮以来根本没有发生改变，那么对于它的所有出边 $(u,v)$，$dis(u)+w(u,v)$ 的值也不会改变，而 $dis(v)$ 只可能变小或不变，因此这些边不可能在这一轮松弛成功。

定理1：只有当一个点 $u$ 的 $dis(u)$ 变小了，以 $u$ 为起点的边 $(u, v)$ 才有可能对后继点 $v$ 进行有效的松弛。

证明：

设在某一时刻，对于边 $(u, v)$ 有 $dis(v) \leqslant dis(u) + w(u,v)$（无法松弛）。 若 $dis(u)$ 没有变小，$dis(v)$ 也没有变大（松弛过程具有单调不增性），则 $dis(v) \leqslant dis(u) + w(u,v)$ 必然持续成立，该边不可能进行有效松弛。 只有 $dis(u)$ 减小，$dis(u) + w(u,v)$ 才可能小于当前的 $dis(v)$。证毕。

因此，我们不需要盲目枚举所有边，只需要维护一个待更新队列：

• 只有 $dis$ 被成功减小的点，才有资格入队去尝试更新它的邻居。
• 用一个队列保存所有“获得了更短路径、需要通知邻居”的点。
• 出队一个点 $u$，扫描它的所有出边 $(u, v)$ 进行松弛；若 $v$ 被更新了且 $v$ 当前不在队列中，则把 $v$ 入队。

这就是 SPFA (Shortest Path Faster Algorithm)，本质上就是队列优化的 Bellman-Ford 算法。

2 图解 SPFA 执行过程

为了直观理解“谁变小了谁去通知邻居”以及“重复入队”的过程，我们来看一个包含负权边的示例有向图（源点为 $1$）：

想换一组边权,或者拿一个带往返负环的图自己跑一遍?试试这个动画:

图中边权如下：

• $1 \to 2$，权值 $5$
• $1 \to 3$，权值 $2$
• $2 \to 4$，权值 $2$
• $3 \to 2$，权值 $-4$
• 点 $5$ 为孤立点（不可达）

2.1 过程演进流程图

2.2 详细步骤追踪表

2.3 图形分析与结论

通过上图可以看到：

1. 重复入队的必要性：点 $2$ 第一次出队时其距离是 $5$；后来经过 $1 \to 3 \to 2$ 发现了一条更短路径（距离为 $-2$）。如果像普通 BFS 那样把访问过的点永久标记为“已访问”，那么点 $4$ 的距离就会永远停留在次优的 $7$，而无法得到最优解 $0$。
2. in_queue 标记的物理含义：in_queue[v] 仅表示“点 $v$ 当前是否在队列排队”。如果已经排在队列中，再次松弛只需直接更新数值 $dis[v]$，无需放入两个相同的点。

3 负环判定的图形解释

当图中存在负权环（环上所有边的权值之和 $< 0$）时：

在上面的图中，环 $2 \to 3 \to 2$ 的总权值为 $(-2) + 1 = -1 < 0$。

• 每在负环上绕一圈，路径总长度就会减少 $1$。
• 这会导致点 $2$ 和点 $3$ 的 $dis$ 可以无限减小下去，因而两点会不断互相松弛、无限次入队与出队，使得普通队列陷入死循环。

计数判定法（边数法）：

• 在一个无负环的图上，任意两点间的最短简单路最多经过 $n$ 个点，即最多经过 $n-1$ 条边（推论1）。
• 我们维护 $cnt[v]$ 表示从源点到点 $v$ 当前最短路径所包含的边数。
• 当通过边 $u \to v$ 松弛成功时，令 $cnt[v] = cnt[u] + 1$。
• 一旦发现某个点的 $cnt[v] \geqslant n$，则说明该路径上至少经过了 $n+1$ 个点，根据抽屉原理必然出现了重复经过的点，即检测到了负环，此时应当立即报告并退出。

4 算法核心过程

1. 初始化：$dis(s) = 0$，其余所有点 $dis(i) = \infty$。
2. 将源点 $s$ 加入队列 $Q$，设置标记 in_queue[s] = true。
3. 循环直到队列为空：
   • 队头元素 $u$ 出队，标记 in_queue[u] = false。
   • 遍历点 $u$ 的所有出边 $(u, v, w)$：
     • 若 $dis(v) > dis(u) + w$：
       • 更新 $dis(v) = dis(u) + w$。
       • 记录经过边数：$cnt(v) = cnt(u) + 1$。
       • 负环判定：若 $cnt(v) \geqslant n$，则说明存在负环，算法直接返回 false。
       • 若 $v$ 不在队列中（即 !in_queue[v]），将 $v$ 入队，并标记 in_queue[v] = true。

5 模板代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include <algorithm>
#include <queue>
#include <vector>

const int maxn = 100000 + 5;
const long long INF = (1LL << 62);

struct edge {
    int to;
    long long w;
};

std::vector<edge> g[maxn];
long long dis[maxn];
int cnt[maxn];       // 当前 dis 对应的历史路径的边数，不是更新次数
bool in_queue[maxn]; // 当前是否在队列中，出队后必须清除

// 点编号为 1..n；换一张图前调用，避免多组数据残留旧边。
void init_graph(int n) {
    for (int u = 1; u <= n; ++u) g[u].clear();
}

void add_edge(int u, int v, long long w) {
    g[u].push_back({v, w});
}

// true：得到单源最短路；false：发现从 s 可达的负环。
// 要求 1 <= s <= n < maxn，所有参与运算的距离与边权和均在 (-INF, INF) 内。
bool spfa(int n, int s) {
    std::fill(dis + 1, dis + n + 1, INF);
    std::fill(cnt + 1, cnt + n + 1, 0);
    std::fill(in_queue + 1, in_queue + n + 1, false);
    std::queue<int> q; // 局部队列保证重复调用时没有上次留下的点

    dis[s] = 0;
    q.push(s);
    in_queue[s] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_queue[u] = false;

        for (const auto& e : g[u]) {
            int v = e.to;
            long long candidate = dis[u] + e.w; // 入队点一定可达
            if (candidate >= dis[v]) continue;

            dis[v] = candidate;
            cnt[v] = cnt[u] + 1;
            if (cnt[v] >= n) return false;

            // 即使 v 已在队列中，也必须先更新 dis 和 cnt。
            if (!in_queue[v]) {
                q.push(v);
                in_queue[v] = true;
            }
        }
    }
    return true;
}

6 负环判定与拓展

关于 SPFA 查找负环的更多原理与证明（边数判定、点更新次数判定、DFS 版 SPFA 对比），见后续章节：负环。

7 相关题解

暂无相关题解