本课时有配套视频讲解，购买后即可观看（永久有效）

SPFA求单源最短路径

一、课上练习

编程练习

负环(SPFA)：L49987

二、知识总结

✨ 核心思想

SPFA（Shortest Path Faster Algorithm）是 Bellman-Ford 的队列优化版本。其核心观察是：在 Bellman-Ford 中，每轮遍历所有边进行松弛，但实际上只有上一轮被更新过的顶点才可能用来松弛其邻居。因此，用一个队列来维护"被更新过的顶点"，只松弛这些顶点的出边。

SPFA 在大多数情况下远快于 Bellman-Ford，但最坏情况仍为 $O(VE)$ ，与 Bellman-Ford 相同。因此在竞赛中，如果边权非负，优先使用 Dijkstra。

✨ 算法原理

初始化：dist[s] = 0，其余 dist[v] = ∞。将源点 $s$ 入队，inQueue[s] = true。
循环处理队列：
- 取出队首顶点 $u$ ，标记 inQueue[u] = false。
- 遍历 $u$ $u$ 的所有出边 $(u, v, w)$ $(u, v, w)$ ，尝试松弛：
  - 如果 dist[u] + w < dist[v]，更新 dist[v]。
  - 如果 $v$ 不在队列中，将 $v$ 入队，标记 inQueue[v] = true。
队列为空时结束。

负环检测：记录每个顶点入队次数 cnt[v]。如果某个顶点入队超过 $V-1$ 次，说明存在负环。或者记录最短路经过的边数，超过 $V-1$ 则存在负环。

SPFA 什么时候用？

场景	推荐算法
边权非负	Dijkstra（堆优化）
有负权边、无负环	SPFA
需要检测负环	SPFA 或 Bellman-Ford
特殊构造的卡 SPFA 数据	Bellman-Ford

✨ 代码实现

1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 100005;
5const long long INF = 1e18;
6
7vector<pair<int, int>> adj[MAXN]; // 邻接表
8long long dist[MAXN];
9bool inQueue[MAXN]; // 是否在队列中
10int cnt[MAXN];      // 入队次数（用于判负环）
11int n, m, s;
12
13bool spfa(int s) {
14    for (int i = 1; i <= n; i++) {
15        dist[i] = INF;
16        inQueue[i] = false;
17        cnt[i] = 0;
18    }
19    dist[s] = 0;
20    inQueue[s] = true;
21    cnt[s] = 1;
22
23    queue<int> q;
24    q.push(s);
25
26    while (!q.empty()) {
27        int u = q.front();
28        q.pop();
29        inQueue[u] = false;
30
31        for (auto [v, w] : adj[u]) {
32            if (dist[u] + w < dist[v]) {
33                dist[v] = dist[u] + w;
34                if (!inQueue[v]) {
35                    q.push(v);
36                    inQueue[v] = true;
37                    cnt[v]++;
38                    // 入队超过n-1次，存在负环
39                    if (cnt[v] >= n) return false;
40                }
41            }
42        }
43    }
44
45    return true; // 无负环
46}
47
48int main() {
49    ios::sync_with_stdio(false);
50    cin.tie(nullptr);
51
52    cin >> n >> m >> s;
53    for (int i = 0; i < m; i++) {
54        int u, v, w;
55        cin >> u >> v >> w;
56        adj[u].push_back({v, w});
57    }
58
59    if (spfa(s)) {
60        for (int i = 1; i <= n; i++) {
61            if (dist[i] == INF)
62                cout << "unreachable";
63            else
64                cout << dist[i];
65            if (i < n) cout << " ";
66        }
67        cout << endl;
68    } else {
69        cout << "NEGATIVE CYCLE" << endl;
70    }
71
72    return 0;
73}

1#include <bits/stdc++.h>
2using namespace std;
3
4const int MAXN = 100005;
5const long long INF = 1e18;
6
7vector<pair<int, int>> adj[MAXN];
8long long dist[MAXN];
9bool inQueue[MAXN];
10int n, m, s;
11
12void spfa_slf(int s) {
13    for (int i = 1; i <= n; i++) {
14        dist[i] = INF;
15        inQueue[i] = false;
16    }
17    dist[s] = 0;
18    inQueue[s] = true;
19
20    // SLF优化：使用双端队列
21    deque<int> dq;
22    dq.push_back(s);
23
24    while (!dq.empty()) {
25        int u = dq.front();
26        dq.pop_front();
27        inQueue[u] = false;
28
29        for (auto [v, w] : adj[u]) {
30            if (dist[u] + w < dist[v]) {
31                dist[v] = dist[u] + w;
32                if (!inQueue[v]) {
33                    inQueue[v] = true;
34                    // SLF策略：如果新距离比队首小，插入队首
35                    if (!dq.empty() && dist[v] < dist[dq.front()])
36                        dq.push_front(v);
37                    else
38                        dq.push_back(v);
39                }
40            }
41        }
42    }
43}

✨ 执行示例

图：5 个顶点，7 条边，源点 $s = 1$ 。

边：1→2(2), 1→3(5), 2→3(-1), 2→4(4), 3→4(2), 3→5(7), 4→5(1)

步骤	队列状态	取出 u	松弛结果
初始	[1]	-	dist[1]=0
1	[] → [2,3]	u=1	dist[2]=2, dist[3]=5
2	[3] → [3,4]	u=2	dist[3]=1(更新), dist[4]=6
3	[4] → [4,5]	u=3	dist[4]=3(更新), dist[5]=8
4	[5] → [5]	u=4	dist[5]=4(更新)
5	[]	u=5	无更新

最终结果：dist = [0, 2, 1, 3, 4]。

注意 dist[3] 从 5 更新为 1（通过负权边 2→3），体现了 SPFA 处理负权边的能力。

✨ 解题步骤详解

建图：邻接表存储，支持负权边。
选择 SPFA 的时机：
- 有负权边时必须用 SPFA（或 Bellman-Ford）。
- 无负权边时不推荐用 SPFA，Dijkstra 更稳定。
负环检测：通过入队次数判断。若只需判断是否有负环（不需要最短路），可以将所有顶点初始距离设为 0，全部入队。
SLF 优化：使用双端队列，将距离小的顶点优先处理，实测可加速 15%-25%。
LLL 优化（Large Label Last）：只出队距离不超过队列平均值的顶点，否则移到队尾。

SPFA 被卡的情况：一些题目专门构造数据卡 SPFA（如网格图、菊花图等）。因此竞赛中若边权非负，务必使用 Dijkstra。

✨ 常见错误

非负权图使用 SPFA：容易被出题人卡到 $O(VE)$ ，应使用 Dijkstra。
忘记 inQueue 标记：不检查 inQueue[v] 会导致同一顶点重复入队，浪费时间。
负环检测阈值错误：入队次数应与 $n$ 比较，不是 $m$ 。
dist 初始化错误：检测全图负环时应将 dist 初始化为 0 并将所有点入队。
SLF 优化中忘记判空：dq.front() 前需确保队列非空。
无向图负权边 = 负环：无向图中任何负权边都会构成负环（来回走即可）。

✨ 算法评价

指标	分析
时间复杂度	平均 $O(kE)$ （ $k$ 为常数），最坏 $O(VE)$
空间复杂度	$O(V + E)$
适用场景	含负权边的稀疏图
优势	实现简单，平均情况快
劣势	最坏情况与 Bellman-Ford 相同，容易被卡
竞赛建议	有负权边时使用，无负权边时用 Dijkstra

SPFA 曾经风靡竞赛界，但随着出题人越来越擅长构造卡 SPFA 的数据，现在的共识是：能用 Dijkstra 就用 Dijkstra，只在有负权边时才用 SPFA。

三、课后练习

编程练习

最小化费：T1344