我的算法书 - SPFA：用队列传播距离更新

一句话算法

谁的距离变小了，就让谁重新通知邻居；用队列保存还没通知完的点。

问题模型

给定一张有向带权图，有 $n$ 个点、 $m$ 条边，点编号为 $1\sim n$ ，源点为 $s$ 。边权可以为负，允许重边和自环。

我们要求从 $s$ 到每个点的最短距离。不可达的点单独标记；如果存在从 $s$ 可达的负环，则报告负环。

负权边可以存在，可达负环会让部分距离没有下界。 沿负环多绕一圈就能减少总代价，因此从负环还能走到的那些点没有有限的最短距离。其他点不一定受影响；本文程序发现可达负环后整体返回失败，不继续分类输出这些点。

阅读前可以先掌握 Bellman-Ford 的松弛操作。

核心直觉：哪些边值得重新检查

对边 $u\to v$ ，权值为 $w$ ，松弛就是检查：

dis[u]+w<dis[v] \quad\Rightarrow\quad dis[v]\gets dis[u]+w.

Bellman-Ford 每轮检查所有边。但假如上次已经用 dis[u] 检查过 u 的所有出边，而 dis[u] 此后没有变化，再检查一遍有什么用？

此时 dis[u] + w 没变，dis[v] 又只可能变小，原来不能改善 v 的边仍然不能改善它。只有 dis[u] 变小，才有必要重新扫描 u 的出边。

于是我们维护一个“待通知队列”：

dis[u] 变小：安排 u 去通知邻居。
取出 u：尝试改善它的每个邻居。
某个邻居的距离又变小：继续安排这个邻居。
队列为空：所有距离变化都已经传播完。

这就是 SPFA（Shortest Path Faster Algorithm），也称队列优化的 Bellman-Ford。它改变了检查边的安排方式，松弛公式保持不变。

为什么不能照搬 BFS 的访问标记

BFS 在等权图中第一次发现一个点，就能确定它的最短距离。SPFA 中，已经出队的点以后仍可能找到更短的路，必须允许再次入队。

in_queue[v] 的含义只有一个：v 当前是否正在排队。

若 v 还在队列里，只更新 dis[v]，无需再放一份 v；等它出队时，会读取最新的距离。若 v 已经出队，则重新排队。

注意：判断 !in_queue[v] 只控制是否入队，不能控制是否松弛。出队时先把 in_queue[u] 清为 false。

手动走一遍

从点 $1$ 出发，按下面的顺序加入边；点 $5$ 没有边：

1 --(5)--> 2 --(2)--> 4
 \        ^
  (2)     |
    \     (-4)
     v    |
       3 -+

边依次为 1 -> 2 (5)、1 -> 3 (2)、2 -> 4 (2)、3 -> 2 (-4)。表中的队列左侧为队头，距离按点 $1\sim 5$ 排列。

本次操作	操作后的距离	操作后的队列
初始化	`0, INF, INF, INF, INF`	`[1]`
取出 1，更新 2、3	`0, 5, 2, INF, INF`	`[2, 3]`
取出 2，更新 4	`0, 5, 2, 7, INF`	`[3, 4]`
取出 3，把 2 从 5 改为 -2	`0, -2, 2, 7, INF`	`[4, 2]`
取出 4，没有出边	`0, -2, 2, 7, INF`	`[2]`
再次取出 2，把 4 从 7 改为 0	`0, -2, 2, 0, INF`	`[4]`
再次取出 4	`0, -2, 2, 0, INF`	`[]`

点 $2$ 第一次出队时，距离还是 $5$ ；后来经由 $1\to3\to2$ 才得到 $-2$ 。如果把它永久标记为“访问过”，更新就传不到点 $4$ 。

算法步骤

所有 dis 设为 INF，令 dis[s] = 0；只有源点入队。
取出队头 u，清除 in_queue[u]。
枚举 g[u] 中的每条边，尝试松弛 v。
松弛成功就更新距离和对应路径的边数；如果发现负环，立即返回失败。
若 v 当前不在队列中，把它加入队尾并设置标记。
重复以上过程，直到队列为空，此时返回成功。

只有距离有限的点才会入队，因此扫描出边时不会拿 INF 参加加法。

怎样让负环不会导致死循环

令 cnt[v] 表示：当前 dis[v] 对应的那次历史路径，一共走了多少条边。 起点为 cnt[s] = 0。每次成功用 u -> v 松弛时：

cpp

        1
2
3

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

这里的“历史路径”是产生这个距离时实际连接起来的路线，允许重复点。以后 u 的距离可能继续变化，但已经赋给 v 的距离和边数仍对应那一次更新；不要求数组中所有点始终组成一棵同步的路径树。

不要把路径边数写成累计松弛次数

cnt[v] = cnt[u] + 1 不能改成 cnt[v]++。例如只有两个点，存在三条 1 -> 2 的边，权值依次为 3、2、1。点 2 可以连续改善三次，但每次对应的路径都只有一条边，图中根本没有环。

算法证明

先考虑从 $s$ 可达的部分没有负环的情况。

1. 距离来自真实路线，不会小于答案

初始的 dis[s] = 0 对应空路径。每次更新只是把一条真实路线接上一条真实边，所以有限的 dis[v] 始终是某条从 $s$ 到 $v$ 的路线长度。

记真正的最短距离为 $\delta(v)$ ，则：

dis[v]\geqslant\delta(v).

2. 队列为空时，所有可达边都不能继续松弛

每个距离变化都会安排一次出边检查。如果点已经在队列中，这次检查会使用它的最新距离。

因此队列为空时，对每条从可达点出发的边都有：

dis[v]\leqslant dis[u]+w(u,v).

沿一条最短路径 $s=p_0\to p_1\to\cdots\to p_k=v$ 连续代入：

dis[v]\leqslant dis[s]+\sum_{i=1}^{k}w(p_{i-1},p_i) =\delta(v).

与上一条合起来，得到 $dis[v]=\delta(v)$ 。从源点出发的更新也会沿路径到达每个可达点，所以只有不可达点会保留 INF。

3. 无负环时为什么会结束

把 FIFO 队列的执行分成若干轮：每轮只处理这一轮开始时已经在队列里的点，新加入队尾的点留给下一轮。因为队列去重，每轮每个点至多处理一次。

源点在第 1 轮传播正确距离。沿任意一条简单最短路径，前一个点的正确距离最迟在下一轮传播给后一个点；如果后一个点仍在本轮队列中，还会更早传播。

没有可达负环时，最短路径可以取为简单路径，最多 $n-1$ 条边。因此经过 $O(n)$ 轮，所有正确距离都会传播完，队列最终清空。

4. 为什么 `cnt[v] >= n` 就能判负环

关键不只是“走了 $n$ 条边就一定有环”，还要解释为什么这个环必然为负。

回看产生某次距离的历史路线，在这条路线第一次重复某个点 $x$ 时，设第一次到达 $x$ 的路线长度为 $D$ ，两次到达之间的环权为 $C$ 。

第一次到达时，算法已经给过 $x$ 一个不超过 $D$ 的距离。此后距离只减不增。第二次到达要成为一次成功的严格松弛，必须满足：

D+C<dis[x]_{\text{更新前}}\leqslant D \quad\Rightarrow\quad C<0.

所以，成功松弛所产生的历史路线一旦重复点，就已经包含负环。 $n$ 条边经过 $n+1$ 个点，必有重复点，判定成立。

反过来，若存在可达负环，队列不可能在所有边都满足松弛不等式时清空：沿负环把这些不等式相加，会得到 $0\leqslant$ 一个负数的矛盾。若边数又始终小于 $n$ ，可用的历史路线只有有限条，严格改善也只能发生有限次，同样矛盾。因此判定最终一定触发。

复杂度分析

每轮扫描的出边总数至多为 $m$ ，最多需要 $O(n)$ 轮，所以 SPFA 最坏时间复杂度为 $O(nm)$ 。计入初始化，完整写法为 $O(n+nm)$ ，也覆盖 $m=0$ 的情况。

有可达负环时，边数判定也会在 $O(n)$ 轮内终止：若运行到第 $n$ 轮结束仍未判出负环，每个被保存的历史路线都少于 $n$ 条边，而 FIFO 分轮传播已覆盖所有少于 $n$ 条边的路线。此时若仍能严格松弛，只能产生至少 $n$ 条边的路线，会触发判定；若不能松弛，则与存在可达负环矛盾。

存图需要 $O(n+m)$ 空间，距离、标记、边数和队列需要 $O(n)$ 额外空间。下面代码预留固定容量，实际分配为 $O(\texttt{maxn}+m)$ 。

队列省去了部分无效检查，但不能保证每条边只检查常数次。不要把复杂度记成 $O(m)$ ，也不能仅凭“稀疏图”判断它足够快。

图的条件	通常采用的方法
所有边权相同且为正	BFS
边权非负的一般图	Dijkstra
有向无环图，边权可负	按拓扑序松弛
一般图含负权边，规模允许 $O(nm)$	Bellman-Ford 或 SPFA

代码模板

使用 std::vector<edge> g[maxn] 存图：g[u] 是点 u 的全部出边，edge 只保存终点和边权。

cpp

        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;
}

调用顺序为 init_graph(n)、逐条 add_edge(u, v, w)、spfa(n, s)。函数返回 true 时读取 dis，其中 INF 表示不可达；返回 false 时不要把当前距离当作最终答案。

同一张图可以换源点重复调用 spfa。多组不同的图则每组先调用 init_graph(n)，清空当前编号范围内的旧边。

距离和边权都使用 long long。INF 必须大于合法的有限距离，且每次 dis[u] + w 都不能溢出；本文完整程序约定 $1\leqslant n\leqslant10^5$ 、 $|w|\leqslant10^9$ 。判负环前保存的路径少于 $n$ 条边，这个范围下 long long 足够。数组容量只决定能存多少点，不代表所有这个规模的图都能在时限内跑完。

代码实现

输入第一行为 n m s，后面 $m$ 行每行 u v w，表示一条有向边。输出一行从源点到 $1\sim n$ 的距离，不可达输出 INF；存在可达负环时，只输出 Negative cycle。

下面是包含读入、输出和 main 的独立程序，可以直接编译。

cpp

        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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

        #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;
}

#include <iostream>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, s;
    if (!(std::cin >> n >> m >> s)) return 0;
    init_graph(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        long long w;
        std::cin >> u >> v >> w;
        add_edge(u, v, w);
    }

    if (!spfa(n, s)) {
        std::cout << "Negative cycle\n";
        return 0;
    }
    for (int v = 1; v <= n; ++v) {
        if (v > 1) std::cout << ' ';
        if (dis[v] == INF) std::cout << "INF";
        else std::cout << dis[v];
    }
    std::cout << '\n';
}

测试用例

1. 负权边、重复入队与不可达点

输入就是前面的手动演示：

输出：

0 -2 2 0 INF

2. 可达负环

输出：

Negative cycle

点 $2\to3\to2$ 的环权为 $-1$ ，并且源点可以到达它。

3. 负环不可达

输出：

0 7 INF INF

负环在另一个连通部分，不影响源点 $1$ 的最短路。只有一个点且没有边时，输入 1 0 1，输出应为 0；若再加一条 1 1 -1 的边，则应报告负环。

应用分类详解

SPFA 维护的是由边约束不断改善的距离；应用时先确定边的含义，再确定哪些点需要成为起点。

一、含负权边的单源最短路

识别信号： 一次转移可能降低总代价，题目给定一个出发点。

把状态作为点，把转移代价作为边权。只有源点初始距离为 $0$ ，其余为 INF。负边不妨碍松弛，但要确认可达负环是否存在，并根据 $O(nm)$ 估算规模。

二、判断循环能否无限降低总代价

识别信号： 题目问是否存在负环，或者能否反复执行同一组操作获得无界收益。

先把收益转换成可相加的边权，再区分检测范围：从某个起点能否到达负环，使用单源初始化；检测整张图，则把所有 dis[i] 和 cnt[i] 设为 $0$ ，所有点都入队并设置标记。

后一种初始化相当于增加一个到所有点都有零权边的超级源点，但没有实际建点；cnt 只数原图的边，阈值仍是 $n$ 。更完整的应用见负环判定。

三、差分约束的可行性

识别信号： 一组约束形如 $x_v-x_u\leqslant w$ ，要求找任意可行解。

改写成 $x_v\leqslant x_u+w$ ，建立边 $u\to v$ ，再用所有点初始为 $0$ 的方式运行。

若有负环，沿环把约束相加得到 $0\leqslant$ 负数，系统无解；若没有负环，队列清空时每条边都满足 dis[v] <= dis[u] + w，取 $x_i=dis[i]$ 就是一组可行解。

经典例题

1. 洛谷 P3371：单源最短路径（弱化版）

题目

用于练习有向邻接表、源点初始化和不可达输出。该题要求不可达时输出 $2^{31}-1$ ，需要修改本文程序的输出约定。题目采用随机数据，适合练习 SPFA 的基本流程；通过这道弱化题并不说明 SPFA 具有稳定的高效率。

2. 洛谷 P3385：负环

luogu-P3385 题解

只判断从点 $1$ 可达的负环，因此保留单源初始化。按题意，非负边添加两个方向，负边只添加输入方向。多组数据需要清空图，并把函数返回值转换成题目要求的 YES 或 NO。

3. 洛谷 P5960：差分约束

luogu-P5960 题解

把 $x_c-x_{c'}\leqslant y$ 转为边 $c'\to c$ ，权值为 $y$ 。这里要检查全部约束，初始化时所有点的距离为 $0$ 并全部入队。出现负环输出无解，否则输出距离数组作为可行解。重点是建边方向和初始化范围。