最短路：Bellman-Ford 与 Floyd-Warshall

前言

上一篇的 Dijkstra 有一个硬性前提：所有边权非负。但现实中有”收益”——走某条路不是付出代价，而是获得奖励（负权边）。比如从城市 A 到城市 B 的运输，走某条路反而能赚 100 元，这相当于权值 $-100$。

Dijkstra 在这种图上会出错。回忆它的贪心证明：$dist[v] \ge dist[u]$，加上非负的边权 $w \ge 0$，所以经过 $v$ 的路径不可能更短。但如果 $w$ 可以是 $-100$，这个论证就崩溃了——经过 $v$ 的路径确实可能更短。

Bellman-Ford 不依赖”非负”假设。它的方法暴力但可靠：对所有边做 $N-1$ 轮松弛。时间 $O(NM)$，比 Dijkstra 慢，但能处理负权边。

Floyd-Warshall 解决另一个问题：不求”从一个起点出发”，而是求所有节点对之间的最短路。三重循环，$O(N^3)$，代码极短。

问题的本质

Dijkstra 的证明在负权时怎么崩溃的？

再看 Dijkstra 的核心论证：取出 $u$（距离最小的未确定节点），声称 $dist[u]$ 已经是最短路。因为任何经过其他未确定节点 $v$ 的路径，长度 $\ge dist[v] \ge dist[u]$。

但如果存在负权边 $v \to u$（权 $-100$），经过 $v$ 的路径长度 $= dist[v] + (-100)$，可能 $< dist[u]$。Dijkstra 的贪心选择不再安全——$u$ 的距离还可能被后续发现的负权边更新。

Bellman-Ford：为什么 N-1 轮就够？

Bellman-Ford 的思路非常直接：对所有边执行松弛操作，重复 $N-1$ 轮。

为什么 $N-1$ 轮就够？ 因为最短路径最多经过 $N-1$ 条边（经过 $N$ 条边必然重复某个节点，形成环。如果是负环，最短路不存在；如果不是负环，去掉环路径更短）。第一轮松弛确定了”经过 1 条边”的最短路，第二轮确定了”经过 2 条边”的，……，第 $N-1$ 轮确定了”经过 $N-1$ 条边”的最短路——这就覆盖了所有可能的最短路。

怎么检测负环？ 再做一轮（第 $N$ 轮）。如果还能松弛，说明存在经过 $N$ 条边的更短路径——这只有在存在负环时才可能。

Floyd-Warshall：三重循环的智慧

Floyd 解决的问题是：给定 $N$ 个节点的加权图（可以有负权边），求每对节点之间的最短路。结果是一个 $N \times N$ 的矩阵，$dist[i][j]$ 是从 $i$ 到 $j$ 的最短距离。

核心思想：逐步允许经过更多的中转节点。$dp[k][i][j]$ 表示”只允许经过节点 $1, 2, \ldots, k$ 作为中转”时 $i$ 到 $j$ 的最短路。转移方程：

$dp[k][i][j] = \min(dp[k-1][i][j],\ dp[k-1][i][k] + dp[k-1][k][j])$

为什么 $k$ 必须是最外层循环？ 因为 $dp[k]$ 只依赖 $dp[k-1]$。如果把 $k$ 放在内层，可能用已经更新过的 $dp[k]$ 值去更新其他节点，导致错误。这和背包问题中”01 背包内层逆序”是同一个道理——依赖关系决定了循环顺序。

用滚动数组优化后，只需要一个二维数组：

$dist[i][j] = \min(dist[i][j],\ dist[i][k] + dist[k][j])$

代码只有三行循环，但背后的 DP 思想非常深刻。

理论 + 代码

Bellman-Ford

#include <cstdio>
#include <cstring>
using namespace std;

typedef long long ll;
const ll INF = 1e18;
const int MAXN = 1006, MAXM = 2006;

struct Edge { int u, v, w; };
Edge edges[MAXM];
ll dist[MAXN];
int N, M;

bool bellman_ford(int start) {
    for (int i = 1; i <= N; i++) dist[i] = INF;
    dist[start] = 0;
    for (int i = 0; i < N - 1; i++) {       // ① N-1 轮
        bool updated = false;
        for (int j = 0; j < M; j++) {
            int u = edges[j].u, v = edges[j].v, w = edges[j].w;
            if (dist[u] < INF && dist[v] > dist[u] + w) { // ② 松弛
                dist[v] = dist[u] + w;
                updated = true;
            }
        }
        if (!updated) break;                // ③ 提前终止
    }
    // 检测负环
    for (int j = 0; j < M; j++) {
        int u = edges[j].u, v = edges[j].v, w = edges[j].w;
        if (dist[u] < INF && dist[v] > dist[u] + w) return false; // ④ 第 N 轮还能松弛 → 负环
    }
    return true;
}

逐行解析：

• ① $N-1$ 轮松弛。为什么是 $N-1$ 不是 $N$？最短路最多经过 $N-1$ 条边（$N$ 个节点不重复的路径）。每轮松弛至少让”经过 $k$ 条边的最短路”被确定一轮。
• ② 松弛条件 dist[u] < INF：如果 $u$ 本身不可达，不能用它去松弛别人。dist[u] + w 可能溢出。
• ③ 如果一轮下来没有任何更新，说明所有最短路已经确定了，提前退出。这是常见优化——实际中很多图不需要跑满 $N-1$ 轮。
• ④ 第 $N$ 轮还能松弛 → 存在负环。负环意味着可以无限绕圈让距离越来越小，最短路不存在。

Floyd-Warshall

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 406;
int dist[MAXN][MAXN];
int N, M;

void floyd() {
    for (int k = 1; k <= N; k++)          // ① 中转点（最外层！）
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); // ② 松弛
}

逐行解析：

• ① $k$ 必须是最外层循环。为什么？因为 DP 的定义是”只允许经过 $1..k$ 作为中转”。如果 $k$ 在内层，更新 $dist[i][j]$ 时可能用到了已经考虑过 $k$ 的 $dist[i][k]$，打破了”只经过 $1..k-1$“的假设。
• ② 核心转移：要么不经过 $k$（直接 $i \to j$），要么经过 $k$（$i \to k \to j$），取较短的。

初始化：dist[i][i] = 0，dist[i][j] = w（如果有边），其余 INF。

三种最短路算法对比

	Dijkstra	Bellman-Ford	Floyd-Warshall
适用图	非负权	任意权（含负）	任意权（含负）
求解目标	单源	单源	全源
时间复杂度	$O((N+M)\log N)$	$O(NM)$	$O(N^3)$
负环检测	❌	✅	需要额外判断
竞赛使用	★★★★★	★★	★★★

选择原则：非负权单源 → Dijkstra，有负权单源 → Bellman-Ford（或 SPFA），全源 → Floyd（$N \le 400$ 时）。

例题

例题 1：Bellman-Ford 基础——有负权边的最短路

场景：$N$ 个城市、$M$ 条单向道路，每条路有一个可能为负的耗时。求从城市 1 到城市 $N$ 的最短时间。如果不可达输出 “unreachable”。

数据范围：$2 \le N \le 1000$，$1 \le M \le 2000$，$-10^9 \le C_i \le 10^9$

分析：标准 Bellman-Ford。边权可能为负，所以 Dijkstra 不适用。

代码：

#include <cstdio>
using namespace std;

typedef long long ll;
const ll INF = 1e18;
const int MAXN = 1006, MAXM = 2006;

struct Edge { int u, v; ll c; } e[MAXM];
ll dist[MAXN];

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; i++)
        scanf("%d%d%lld", &e[i].u, &e[i].v, &e[i].c);
    for (int i = 1; i <= N; i++) dist[i] = INF;
    dist[1] = 0;
    for (int i = 1; i < N; i++)           // ① N-1 轮
        for (int j = 0; j < M; j++)
            if (dist[e[j].u] < INF)
                if (dist[e[j].v] > dist[e[j].u] + e[j].c)
                    dist[e[j].v] = dist[e[j].u] + e[j].c;
    if (dist[N] == INF) printf("unreachable\n");
    else printf("%lld\n", dist[N]);
    return 0;
}

逐行解析：

• ① $N-1$ 轮松弛保证：如果无负环，最短路最多经过 $N-1$ 条边，$N-1$ 轮后一定收敛。

---

例题 2：负环检测

场景：$N$ 个城市，$M$ 条单向道路（边权可正可负）。判断从城市 1 出发，是否存在可以被利用的负环（即从 1 能到达的负环）。

数据范围：$1 \le N \le 500$，$1 \le M \le 1000$

代码：

#include <cstdio>
using namespace std;

typedef long long ll;
const ll INF = 1e18;
const int MAXN = 506, MAXM = 1006;

struct Edge { int u, v; ll c; } e[MAXM];
ll dist[MAXN];

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; i++)
        scanf("%d%d%lld", &e[i].u, &e[i].v, &e[i].c);
    for (int i = 1; i <= N; i++) dist[i] = INF;
    dist[1] = 0;
    // ① N-1 轮正常松弛
    for (int i = 1; i < N; i++)
        for (int j = 0; j < M; j++)
            if (dist[e[j].u] < INF)
                if (dist[e[j].v] > dist[e[j].u] + e[j].c)
                    dist[e[j].v] = dist[e[j].u] + e[j].c;
    // ② 第 N 轮：还能松弛说明有负环
    bool neg = false;
    for (int j = 0; j < M; j++)
        if (dist[e[j].u] < INF && dist[e[j].v] > dist[e[j].u] + e[j].c)
            neg = true;
    printf("%s\n", neg ? "NEGATIVE CYCLE" : "OK");
    return 0;
}

逐行解析：

• ② 第 $N$ 轮额外检查：如果还能松弛，说明存在可以无限降低距离的环。由于只有从起点可达的节点 dist 不是 INF，所以只会检测从起点可达的负环。

---

例题 3：Floyd-Warshall 基础

场景：$N$ 个城市，$M$ 条双向道路。$Q$ 个查询：从城市 $A_i$ 到城市 $B_i$ 的最短距离。

数据范围：$2 \le N \le 400$，$1 \le M \le N(N-1)/2$，$1 \le Q \le 10^5$

分析：$N \le 400$，Floyd 的 $O(N^3) = 6.4 \times 10^7$ 刚好能过。$Q$ 次查询直接查 dist[A][B]。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;
const ll INF = 1e18;
const int MAXN = 406;

ll dist[MAXN][MAXN];

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            dist[i][j] = (i == j) ? 0 : INF; // ① 初始化
    for (int i = 0; i < M; i++) {
        int a, b; ll c;
        scanf("%d%d%lld", &a, &b, &c);
        dist[a][b] = min(dist[a][b], c);     // ② 处理重边
        dist[b][a] = min(dist[b][a], c);
    }
    // ③ Floyd
    for (int k = 1; k <= N; k++)
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                if (dist[i][k] < INF && dist[k][j] < INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    int Q;
    scanf("%d", &Q);
    while (Q--) {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%lld\n", dist[a][b] == INF ? -1 : dist[a][b]);
    }
    return 0;
}

逐行解析：

• ① 自己到自己是 0，其余初始化为 $\infty$。
• ② min 处理重边。
• ③ Floyd 三重循环。注意 dist[i][k] < INF 检查防止从不可达点中转。

---

例题 4：传递闭包

场景：$N$ 个元素的偏序关系。$M$ 条有向边表示”$a$ 在 $b$ 之前”。$Q$ 个查询：$a$ 是否在 $b$ 之前（直接或间接）？

分析：Floyd 的变体——传递闭包。把 dist[i][j] 改成 bool 值（可达/不可达）。

bool reach[MAXN][MAXN];
// 初始化：reach[i][j] = (i==j) || 有边 i→j
for (int k = 1; k <= N; k++)
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);

这和 Floyd 的结构完全一样，只是把 min(+) 换成了 ||(&&)。

参考文献

教材讲解 — 競技プログラミングの鉄則 第 9 章

• 9.4 Dijkstra 法（Bellman-Ford、Floyd-Warshall 为课堂扩展内容）

系统练习 — 競技プログラミングの鉄則

• A64 Shortest Path 2（加权最短路，Dijkstra）
• B64 Shortest Path with Restoration（路径还原）

实战练习 — 競プロ典型 90 問

• 013 Passing（★5，双向 Dijkstra）

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化