最短路算法选型指南：Dijkstra、SPFA 与 Floyd 的适用边界

发表于 分类于
从BFS为什么失效讲起，理清Dijkstra、SPFA、Bellman-Ford与Floyd的适用边界，并给出负权反例与常见翻车点。

带权图上求”两点间路径长度最小”，看起来是一个搜索问题，但算法选错了，轻则超时、重则答案错。这篇文章把竞赛里最常考的几个最短路算法摊开讲清楚：它们各自的正确性前提是什么、边界在哪里、什么时候必须换算法。

带权有向图上的最短路径示意

一、问题背景：为什么不能拿 BFS 去顶

很多同学的第一个想法是：BFS 逐层扩展，第一次到达就是最短路，多简单啊。

BFS 的正确性建立在一个极其苛刻的前提上：每条边的”长度”都相同。层数就等价于路径经过的边数，边数最少自然长度最短。一旦边权不同，”经过 1 条权值 100 的边”和”经过 10 条权值 1 的边”谁更短，BFS 完全无从判断——它只数层。

一个最小反例：

1
2
1 --(100)--> 2 --(1)--> 4
1 --(1)--> 3 --(1)--> 5

问 1 到 4 的最短距离。BFS 先访问到 2（1 步），答案是 1；真实最短路是 1→3→5→... 不存在通路，退一步说若还有 1→3→X→4 各 1，总代价 3，仍然比 100 小。结论很硬：只要图里有非 0 权边，BFS 的答案就没有任何参考价值。

那能不能”改造”BFS？比如用一个有序容器，每次弹出当前距离最小的点——这正是 Dijkstra 的核心思想。所以 BFS 不是被”改进”成 Dijkstra，而是被替换成 Dijkstra。

二、思路：四个算法，四套前提

2.1 Dijkstra：非负权，单源，贪心

核心过程只有四行：

  1. dist[s] = 0，其余为 INF；
  2. 用小根堆取出当前 dist 最小的未确定点 u；
  3. 用 u 去松弛（relax）所有出边：dist[v] = min(dist[v], dist[u] + w)；
  4. 重复直到堆空。

“松弛”这个词要理解成：我现在知道了一条到达 u 的路径，尝试用它去改进 v 的答案。整个算法就是不断重复”拿当前最有把握的结论去推断邻居”。

非负权是正确性前提，理由在下一节的正确性证明里讲。

堆优化后复杂度 O(m log n)，是绝大多数竞赛场景的默认选择。

2.2 SPFA：允许负权，但别指望它快

SPFA 本质是 Bellman-Ford 的队列化实现：把队列里取出的点 u 的所有出边松弛一次，被成功松弛的 v 重新入队。它是”用改动驱动”的写法，只有真正被改善的点才会再次向外传播，所以通常比朴素 Bellman-Ford 的 O(VE) 快。

但现实是这样的：

  • 期望复杂度约 O(kE)，k 是入队次数均值；
  • 最坏仍然是 O(VE)，而且这个最坏是可以被构造出来的（学术上叫”SPFA 已被 Kill”）。

典型的卡人手法是：设计一组让某个点反复入队、每次只被改善 1 的边权。结论：题目不保证”图很善良”时，不要把 SPFA 当主力。NOIP/CSP 的数据里 SPFA 被卡是常态。另外，如果存在负环，SPFA 会一直转，必须用 cnt[v] = cnt[u] + 1，一旦 cnt[v] >= n 就判定存在负环。

2.3 Bellman-Ford：负权的兜底

朴素 Bellman-Ford 做 n 轮松弛，每轮扫全部边：

1
2
3
for i = 1..n:
    for each (u,v,w):
        dist[v] = min(dist[v], dist[u] + w)

第 n 轮仍然发生松弛 ⇒ 存在从源点可达的负环。复杂度 O(VE)，只适合 VE 在千万级的小图。SPFA 是它的工程改良，不是理论改进。

2.4 Floyd：全源最短路，O(V³)

Floyd 用三重循环做”中转点”枚举：

1
2
3
4
for k in 1..n:            // 枚举中转点 k
  for i in 1..n:          // 枚举起点 i
    for j in 1..n:        // 枚举终点 j
      d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

为什么 k 必须在最外层？因为 Floyd 的状态定义是 d[i][j] 表示只允许编号 < k 的点作为中间点时 i 到 j 的最短距离。k 在最外层，才能保证读 d[i][k]、d[k][j] 时它们已经是”允许用到第 k 个中转点之前”的最优值。把 k 放在内层是初学者最常见的错误之一，写完后一定会 WA。

规模判断：n = 400 时 400³ = 6.4×10⁷，C++ 跑得动；n = 1000 时 10⁹，开始吃力；n = 5000 时 1.25×10¹¹，直接放弃。Floyd 的舒适区就是 n ≤ 400~500 量级。 好消息是 Floyd 天然支持负权（但不支持负环判定的直接用法，需额外判断）。

三、正确性：Dijkstra 为什么在负权上会给出错误答案

Dijkstra 的贪心论证是这样的：每轮取出的 dist 最小的点 u，我们断言 dist[u] 就是真实最短距离。支持这个断言的推理是：

若存在一条更短的路径到达 u，那条路径上一定存在某个点 v，使得 dist[v] < dist[u]，且 v 在 u 之前被取出（否则 u 会先于它被取出）。

关键在”v 的真实距离 ≤ u 的真实距离 < dist[u]”这一步，它用的是 边权非负：沿路径往前走过一条边不会让距离变大，所以越靠近源点的中间点，其距离不会超过终点的距离。一旦有负边，”沿路径往前走距离不会变大”这个前提就崩了，贪心断言失效。

来看一个只有 4 个点、能让 Dijkstra 明确算错的例子（源点 1）：

边权值
1 → 22
1 → 35
3 → 2-4
2 → 43

真实最短路是 1→3→2→4，长度 5 + (-4) + 3 = 4。

Dijkstra 的实际执行过程：

步骤动作dist[2]dist[3]dist[4]
初始松弛 1 的出边25INF
1取出 dist 最小的 2（值 2），确定，松弛 2→42（已确定）55
2取出 3（值 5），松弛 3→2：5-4=1 < 2，若重算能得 1，但已来不及1（已过期）55
3取出 4——5

Dijkstra 最终输出 dist[4] = 5，而正确答案是 4。

错因要分两层说清楚，因为这里有个常见困惑：既然 3 晚到一步松弛出了更好的 dist[2]，为什么答案还是错的？

  • 朴素实现里，点 2 在第 1 轮就被 visited 标记”确定”，第 2 轮的更新被直接丢弃；
  • 惰性删除（堆优化）实现里，dist[2] 数组里确实被改成了 1，但点 4 的松弛早在第 1 轮就做完了，而 dist[4] 之后再也不会被重新松弛——因为 Dijkstra 的结构里，一个点出堆后不再回溯。

一句话：点 2 在拿到最优解之前就被”提前定死”了，此后到达它的更优路径无法再传播到 4。

结论记住三条：

  1. 边权非负 → Dijkstra；
  2. 存在负权、无负环 → Bellman-Ford / SPFA（或用 Johnson 算法做全源负权最短路）；
  3. DAG 上的最短路不用管负负权，直接按拓扑序 DP，这是 DAG 题的标准解法。

四、复杂度与选型：稠密图 vs 稀疏图

设点数 n、边数 m：

算法复杂度适用规模负权多源
BFSO(n+m)任意不适用（无权）支持（多源 BFS）
Dijkstra（堆优化）O(m log n)稀疏图 m ≈ n~2n❌单源
Dijkstra（朴素）O(n²)稠密图 m ≈ n²❌单源
SPFA期望 O(k·m)，最坏 O(nm)小图 / 图很善良✅单源
FloydO(n³)n ≤ 400✅全源

稠密图选朴素 Dijkstra。 当 m ≈ n² 时，堆里塞了 O(m) 个元素，每个 log 操作都在给 O(n²) 的量级再加常数；而朴素 Dijkstra 每轮扫数组找最小值是 O(n)，总 O(n²)，常数极小。实测 n = 2000 的稠密图，朴素版往往比堆优化还快。判断标准很简单：m > n²/ log n 就考虑朴素版。

稀疏图选堆优化 Dijkstra。 m = O(n) 时 O(m log n) ≈ O(n log n)，比 O(n²) 快一个数量级。

记忆口诀：稀疏堆、稠密扫、负权 SPFA、全源 Floyd、小规模 Bellman。

五、long long 开销与 INF 取值的坑

5.1 0x3f3f3f3f 不是完美的 INF

0x3f3f3f3f ≈ 1.0611×10⁹。这个常量好用的地方是：二进制形如 0011...，memset 一个字节 0x3f 就能把整个数组填满，且 0x3f3f3f3f + 0x3f3f3f3f = 0x7e7e7e7e，在 int 范围内不会溢出——所以它当年很流行。

隐患有两个，都会在特定数据下翻车：

  1. 答案本身超过 1.06×10⁹ 就废了。题目没保证路径权值和不超过 INF，而 INF 的语义却是”比任何合法答案都大”。稳妥做法是 const long long INF = (1LL << 62);，或者根据 Σ max(w, 0) 估一个上界。
  2. 加法溢出。INF + w 若 w 是较大的正数（超过 1.06×10⁹）就可能溢出成负数。标准做法是每次松弛前先判断起点是否可达：
1
if (dist[u] == INF) continue;      // 别让 INF 参与加法
  1. Floyd 里忘了判 INF，是本题最经典的 WA 来源：若有 d[i][k] == INF 而 d[k][j] 是负数，INF + 负数 < INF，于是这条不可达路径被”更新”成一个伪有限值，随后继续污染整个矩阵。Floyd 的内层必须有 INF 守卫。

5.2 要不要开 long long

long long 占 8 字节，是 int 的两倍，邻接表结构从 12 字节涨到 16 字节，缓存命中率会下降——在极限数据下这可能是可测量的常数损失。

给学生的判断标准：

场景建议
边权上界明确（如 ≤ 1000），且 n × w_max < 2^31int 足够
边权可达 1e9，或存在多条路径权值累加必须 long long
Floyd（n² 个值，且最短路可能绕圈累加）一律 long long
距离可能被乘（如期望值 DP）一律 long long

结论：不确定就用 long long。 省下的那点内存，远不如一次 WA 的代价大。

六、参考代码（C++17）

下面这份程序把四种算法放进一个可切换的实现里，命令行参数 mode 决定行为：dijkstra（堆优化）、dijkstra-dense（朴素）、spfa、floyd。适合直接拿去改成题目需要的版本。

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = (1LL << 62);   // 足够大，且 INF + INF 不溢出 long long

struct Edge {
    int to;
    ll w;
    bool operator<(const Edge& other) const {
        return w > other.w;   // 小根堆：priority_queue 默认是大根堆，反转比较器
    }
};

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

    int n, m, s;
    cin >> n >> m >> s;
    --s;  // 统一转成 0-based

    vector<vector<Edge>> g(n);
    vector<vector<ll>> d(n, vector<ll>(n, INF));
    for (int i = 0; i < n; ++i) d[i][i] = 0;

    for (int i = 0; i < m; ++i) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        --u; --v;
        g[u].push_back({v, w});   // 有向边
        d[u][v] = min(d[u][v], w);
    }

    string mode;
    cin >> mode;

    if (mode == "dijkstra") {
        // ---- 堆优化 Dijkstra：要求边权非负 ----
        vector<ll> dist(n, INF);
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
        dist[s] = 0;
        pq.push({0, s});

        while (!pq.empty()) {
            auto [du, u] = pq.top();
            pq.pop();
            if (du != dist[u]) continue;   // 过期条目，跳过
            for (const auto& e : g[u]) {
                if (dist[e.to] > du + e.w) {
                    dist[e.to] = du + e.w;
                    pq.push({dist[e.to], e.to});
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            if (dist[i] == INF) cout << "INF\n";
            else cout << dist[i] << '\n';
        }
    } else if (mode == "dijkstra-dense") {
        // ---- 朴素 Dijkstra：O(n^2)，适合稠密图 ----
        vector<ll> dist(n, INF);
        vector<bool> used(n, false);
        dist[s] = 0;
        for (int it = 0; it < n; ++it) {
            int u = -1;
            for (int i = 0; i < n; ++i) {
                if (!used[i] && (u == -1 || dist[i] < dist[u])) u = i;
            }
            if (u == -1 || dist[u] == INF) break;
            used[u] = true;              // 此处"提前定死"，负权下就是错的来源
            for (const auto& e : g[u]) {
                if (dist[e.to] > dist[u] + e.w) dist[e.to] = dist[u] + e.w;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (dist[i] == INF) cout << "INF\n";
            else cout << dist[i] << '\n';
        }
    } else if (mode == "spfa") {
        // ---- SPFA：允许负权，最坏 O(VE) ----
        vector<ll> dist(n, INF);
        vector<int> cnt(n, 0);
        vector<bool> inq(n, false);
        queue<int> q;
        dist[s] = 0;
        q.push(s);
        inq[s] = true;

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            inq[u] = false;
            for (const auto& e : g[u]) {
                if (dist[e.to] > dist[u] + e.w) {
                    dist[e.to] = dist[u] + e.w;
                    // cnt[v] 记录"最短路径上的边数"，达到 n 说明存在可达负环
                    cnt[e.to] = cnt[u] + 1;
                    if (cnt[e.to] >= n) {
                        cout << "NEGATIVE CYCLE\n";
                        return 0;
                    }
                    if (!inq[e.to]) {
                        inq[e.to] = true;
                        q.push(e.to);
                    }
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            if (dist[i] == INF) cout << "INF\n";
            else cout << dist[i] << '\n';
        }
    } else if (mode == "floyd") {
        // ---- Floyd：O(n^3)，全源最短路，支持负权 ----
        // 注意 k 必须在最外层
        for (int k = 0; k < n; ++k) {
            for (int i = 0; i < n; ++i) {
                if (d[i][k] == INF) continue;    // 关键守卫：INF 不参与加法
                for (int j = 0; j < n; ++j) {
                    if (d[k][j] == INF) continue;
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            if (d[i][s] == INF) cout << "INF\n";
            else cout << d[i][s] << '\n';
        }
    } else {
        cout << "unknown mode\n";
        return 0;
    }
    return 0;
}

输入格式：第一行 n m s（点数、边数、源点），接着 m 行 u v w，最后一行是模式字符串。输入保证边权非负时才能用两种 Dijkstra；只有 spfa 与 floyd 支持负权。

七、易错点清单

  1. 在负权图上用 Dijkstra。会用”样例过了”掩盖问题，一定要自己构造反例验证，第三节那张表就是模板。
  2. 漏判源点是否可达就做加法。dist[u] == INF 时 INF + w 可能溢出或污染答案。
  3. Floyd 把 k 写在内层，状态定义直接崩掉。
  4. Floyd 内部不判 INF，负权下不可达路径被更新成垃圾值。
  5. INF 定得太小，合法答案超过 0x3f3f3f3f。用 1LL << 62 更省心。
  6. 用 SPFA 赌大数据。除非能证明图的性质（如”边权为 0/1 的网格图”、DAG），否则优先想 Bellman-Ford 分层或换建模方式。
  7. 堆优化里忘了 if (du != dist[u]) continue;，堆里堆着大量过期条目，常数暴涨（虽然还能算对）。
  8. 稠密图硬套堆优化，白白多付 log 因子的钱。
  9. 无向图忘记建双向边，写成 g[u].push_back(...) 一次。
  10. “多源”需求硬套单源算法。多源最短路（离最近的源点）用多源 BFS 或把所有源点入堆、初始 dist = 0，不要逐个源点跑一遍。