最短路径：图上的距离

Part 1”探”建立了一整套看清图结构的工具：BFS/DFS 遍历每个角落，连通性分析找出桥和强连通分量，拓扑排序理清 DAG 上的依赖顺序，树算法在极简骨架上实现高效查询。但”看清结构”只是起点——现在我们要在图上度量。

进入 Part 2”量”。第一个问题，也是最基本的度量问题：给定一张加权图，两个节点之间的最短距离是多少？

这个问题无处不在。导航 App 计算驾车路线、网络路由器选择数据包的转发路径、社交网络分析两人之间的”距离”、编译器优化计算关键路径——归根结底都是在回答同一个问题。不同的约束条件（边权是否为负？是否需要所有点对的距离？图是否有特殊结构？）催生了一系列不同的算法。本文就是这个”最短路径工具箱”的完整指南。

算法范式：贪心（Dijkstra）、动态规划（Floyd-Warshall）、迭代逼近（Bellman-Ford）

核心问题：两点之间，最便宜的路？

给定加权有向图 $G = (V, E)$，每条边 $e = (u, v)$ 有权重 $w(u, v)$（可以理解为”通行代价”）。定义从 $u$ 到 $v$ 的一条路径 $p = \langle v_0, v_1, \ldots, v_k \rangle$ 的权重为

$w(p) = \sum_{i=1}^{k} w(v_{i-1}, v_i)$

从 $u$ 到 $v$ 的最短路径距离（shortest-path distance）定义为

$d(u, v) = \begin{cases} \min\{w(p) : p \text{ 是 } u \to v \text{ 的路径}\} & \text{如果存在路径} \\ \infty & \text{否则} \end{cases}$

无权图是权重全为 1 的特例——这时 $d(u, v)$ 就是最少跳数，BFS 已经解决了（Art. 1）。但当边权不均匀时，BFS 的”逐层扩展”不再保证最短路。

为什么不同约束需要不同工具？ 因为每种算法都利用了特定的结构性质来加速：

• 无权图 → BFS：$O(V+E)$，逐层扩展天然最短
• 非负权图 → Dijkstra：利用”已确定的不会再变”的贪心性质
• 有负权边 → Bellman-Ford：贪心失效，但迭代逼近仍可收敛
• 全对最短路 → Floyd-Warshall：DP 视角，$O(V^3)$ 解决所有点对
• 有启发式 → A*：用估价函数导向搜索，减少无关探索
• DAG → 拓扑序松弛：$O(V+E)$，无环保证一遍搞定

核心操作：松弛（Relaxation）

在讲具体算法之前，先理解一个贯穿所有最短路径算法的核心操作——边松弛（edge relaxation）。

什么是松弛？

维护一个距离估计数组 $d[v]$，初始时 $d[s] = 0$（源点），$d[v] = \infty$（其余节点）。对于一条边 $(u, v)$，松弛操作检查：经过 $u$ 到 $v$ 是否比当前已知的到 $v$ 的最短路径更短？

Relax(u, v, w):
    if d[v] > d[u] + w(u, v):
        d[v] = d[u] + w(u, v)
        parent[v] = u

如果 $d[v] > d[u] + w(u, v)$，说明三角不等式（triangle inequality）被违反了——系统处于一种”不平衡”的状态。更新 $d[v]$ 后，违反消除，系统恢复平衡。

弹簧类比

“松弛”这个名字来自一个物理类比：把 $d[v]$ 想象成一根弹簧的当前长度。如果三角不等式被违反（$d[v] > d[u] + w(u, v)$），弹簧被过度拉伸，处于紧张状态（tense）。执行松弛操作就像让弹簧缩回到自然长度——系统”放松”（relax）了。

所有最短路径算法的本质区别在于：以什么顺序、对哪些边执行松弛操作。

• Dijkstra：按距离从小到大的顺序，每个节点只松弛一次其出边
• Bellman-Ford：反复对所有边松弛 $|V| - 1$ 轮
• DAG 松弛：按拓扑序，每个节点松弛一次其出边
• Floyd-Warshall：用 DP 的方式，逐步增加可用中间节点来松弛

单源无权最短路：BFS（回顾）

对于无权图（所有边权为 1），Art. 1 已经给出了最优解——BFS。BFS 从源点 $s$ 出发逐层扩展，每个节点首次被发现时的层数就是到 $s$ 的最短距离。

• 时间：$O(V + E)$
• 空间：$O(V)$
• 条件：所有边权相同（或无权）

这是最快的最短路径算法，因为它利用了”所有边等价”这一最强约束。一旦边权不一致，BFS 就不再正确——因为”跳数少”不等于”总权重小”。

单源非负权最短路：Dijkstra 算法

核心思想

Dijkstra 算法（1959）是加权图上最重要的单源最短路径算法。它的核心是一个贪心策略：

维护一个”已确定最短距离”的节点集合 $S$。每次从未确定的节点中选出 $d[v]$ 最小的那个，将它加入 $S$（确定其最短距离），然后松弛它的所有出边。

为什么这个贪心策略正确？关键假设是边权非负：一旦一个节点 $v$ 被从优先队列中取出，不可能再找到更短的路径到达 $v$——因为更短的路径必须经过某个 $d$ 更大的中间节点，而经过该中间节点的路径长度只会更大（边权非负）。

算法流程

Dijkstra(G, s):
    for each v ∈ V:
        d[v] = ∞
        parent[v] = nil
    d[s] = 0
    PQ = min-priority queue with all v, keyed by d[v]

    while PQ is not empty:
        u = PQ.extract-min()       // 贪心选择
        for each edge (u, v) ∈ E:
            if d[v] > d[u] + w(u, v):  // 松弛
                d[v] = d[u] + w(u, v)
                parent[v] = u
                PQ.decrease-key(v, d[v])

复杂度分析

Dijkstra 的复杂度取决于优先队列的实现：

优先队列实现	extract-min	decrease-key	总时间
数组（线性扫描）	$O(V)$	$O(1)$	$O(V^2)$
二叉堆	$O(\log V)$	$O(\log V)$	$O((V+E)\log V)$
Fibonacci 堆	$O(\log V)$ 均摊	$O(1)$ 均摊	$O(V\log V + E)$

• 稠密图（$E \approx V^2$）：数组版 $O(V^2)$ 反而最快
• 稀疏图（$E \approx V$）：二叉堆版 $O(V \log V)$ 最实用
• Fibonacci 堆理论最优，但常数因子大，实践中很少使用
• 最常用：二叉堆版 $O((V+E)\log V)$

数值走查

以上面的图为例，从 $S$ 出发做 Dijkstra：

1. 初始：$d = [S{:}0, A{:}\infty, B{:}\infty, C{:}\infty, D{:}\infty, E{:}\infty]$，PQ 取出 $S$
2. 松弛 S 的出边：$d[A] = 4$，$d[B] = 2$
3. PQ 取出 B（d=2）：松弛 $B \to A$：$d[A] = \min(4, 2+1) = 3$；松弛 $B \to D$：$d[D] = 7$
4. PQ 取出 A（d=3）：松弛 $A \to C$：$d[C] = 6$；松弛 $A \to E$：$d[E] = 10$
5. PQ 取出 C（d=6）：松弛 $C \to E$：$d[E] = \min(10, 6+2) = 8$
6. PQ 取出 D（d=7）：松弛 $D \to E$：$d[E] = \min(8, 7+1) = 8$；松弛 $D \to C$：$d[C] = \min(6, 7+1) = 6$
7. PQ 取出 E（d=8）：无更新

最终：$d = [0, 3, 2, 6, 7, 8]$。

为什么负权边破坏 Dijkstra？

Dijkstra 的正确性依赖一个关键假设：一个节点一旦从优先队列中被取出（确定），它的 $d$ 值就是最终的最短距离。这在所有边权非负时成立。

但如果存在负权边，这个假设就不成立了——一个”已确定”的节点可能通过某条负权边被进一步缩短。

在这个例子中：

• Dijkstra 先确定 $B$（$d = 2$，通过 $S \to B$），因为 2 < 4
• 然后确定 $A$（$d = 4$，通过 $S \to A$）
• 但此时 $B$ 已经”锁定”了，不会再检查 $A \to B$ 这条边
• 实际上 $S \to A \to B$ 的距离是 $4 + (-3) = 1 < 2$

这就是贪心在负权下的失效——“局部最优”不再保证”全局最优”。

单源有负权最短路：Bellman-Ford 算法

核心思想

当存在负权边时，贪心失效了。Bellman-Ford（1958）用一种更保守但更通用的策略——迭代逼近：

对所有边反复执行松弛操作，重复 $|V| - 1$ 轮。

为什么是 $|V| - 1$ 轮？因为在没有负权环的图中，任何最短路径最多包含 $|V| - 1$ 条边（经过每个节点最多一次）。第 $k$ 轮保证了所有最多包含 $k$ 条边的最短路径被正确计算。所以 $|V| - 1$ 轮后，所有最短路径都被找到。

算法流程

BellmanFord(G, s):
    for each v ∈ V:
        d[v] = ∞
    d[s] = 0

    // 松弛 |V|-1 轮
    for i = 1 to |V| - 1:
        for each edge (u, v) ∈ E:
            if d[u] ≠ ∞ and d[v] > d[u] + w(u, v):
                d[v] = d[u] + w(u, v)
                parent[v] = u

    // 负权环检测：第 |V| 轮
    for each edge (u, v) ∈ E:
        if d[u] ≠ ∞ and d[v] > d[u] + w(u, v):
            return "存在负权环"

    return d, parent

为什么能处理负权边？

Bellman-Ford 没有”贪心锁定”的概念——每一轮都重新审视所有边。如果第 2 轮发现了一条经过负权边的更短路径，它会更新 $d$ 值，而这个更新会在后续轮次中继续传播。

关键是：迭代逼近不依赖贪心假设。它只依赖一个更弱的事实——“最短路径最多 $|V| - 1$ 条边”——而这在无负权环的图中始终成立。

负权环检测

如果图中存在负权环（negative-weight cycle，即一个环的边权之和为负），那么最短路径不存在——你可以沿着负权环无限绕圈，让路径长度趋向 $-\infty$。

Bellman-Ford 有一个优雅的检测方法：在 $|V| - 1$ 轮之后再做第 $|V|$ 轮。如果这一轮仍然能松弛某条边，说明存在负权环——因为无负权环时 $|V| - 1$ 轮一定已经收敛。

SPFA 优化

SPFA（Shortest Path Faster Algorithm）是 Bellman-Ford 的队列优化版本。核心观察：只有当 $d[u]$ 在上一轮被更新过时，从 $u$ 出发的松弛才可能有效。

SPFA(G, s):
    d[s] = 0, 其余 ∞
    Q = queue containing s
    inQueue[s] = true

    while Q not empty:
        u = Q.dequeue()
        inQueue[u] = false
        for each edge (u, v):
            if d[v] > d[u] + w(u, v):
                d[v] = d[u] + w(u, v)
                if not inQueue[v]:
                    Q.enqueue(v)
                    inQueue[v] = true

SPFA 的平均复杂度远好于 $O(VE)$（接近 $O(E)$），但最坏情况仍然是 $O(VE)$——在某些精心构造的图上，SPFA 会退化。因此在竞赛中 SPFA 受欢迎，但工程实践中通常选择 Dijkstra（非负权）或标准 Bellman-Ford（有负权）。

复杂度

• 时间：$O(VE)$（最坏情况）
• 空间：$O(V)$
• 优势：能处理负权边，能检测负权环

交互式走查

下面的组件在同一张加权图上展示 Dijkstra 和 Bellman-Ford 的完整执行过程。切换算法观察它们的不同策略：Dijkstra 按距离从小到大贪心确定，Bellman-Ford 反复对所有边松弛。

最短路径算法走查

DijkstraBellman-Ford

步骤 1/28: 初始化：d(S)=0，其余 ∞。优先队列 PQ = {S:0}

重置

1 / 28上一步下一步

注意关键区别：

• Dijkstra 每步只处理一个节点的出边（贪心选最近的），节点一旦标绿（确定）就不再改变
• Bellman-Ford 每轮扫描所有边，可能多次更新同一个节点的距离

全对最短路：Floyd-Warshall 算法

问题变化

前面的算法都是单源的——给定一个起点 $s$，求 $s$ 到所有其他节点的最短距离。如果我们需要所有点对之间的最短距离呢？

朴素方法：对每个节点做一次 Dijkstra（或 Bellman-Ford），总计 $O(V \cdot (V+E)\log V)$ 或 $O(V^2 E)$。对于稠密图，Floyd-Warshall 提供了一个更优雅且常数因子更小的 $O(V^3)$ 解法。

核心思想

Floyd-Warshall（1962）的 DP 状态设计是全对最短路的经典：

$d_k(i, j)$ = 从 $i$ 到 $j$，只允许经过编号 $\le k$ 的节点作为中间节点的最短路径长度

转移方程：

$d_k(i, j) = \min\big(d_{k-1}(i, j),\;\; d_{k-1}(i, k) + d_{k-1}(k, j)\big)$

直觉：当考虑增加节点 $k$ 作为可用中间节点时，从 $i$ 到 $j$ 的最短路径要么不经过 $k$（保持原值），要么经过 $k$（先到 $k$ 再从 $k$ 到 $j$）。取两者的较小值。

算法流程

FloydWarshall(G):
    // 初始化：直接边
    for each (i, j):
        if i == j: d[i][j] = 0
        elif (i, j) ∈ E: d[i][j] = w(i, j)
        else: d[i][j] = ∞

    // DP：逐步增加可用中间节点
    for k = 1 to |V|:
        for i = 1 to |V|:
            for j = 1 to |V|:
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    return d

注意三重循环的顺序——$k$ 必须在最外层。这不是任意的：$k$ 代表”当前可用的中间节点集合的上界”，它定义了 DP 的阶段（stage）。

数值走查

初始图：$A \xrightarrow{3} B \xrightarrow{2} C \xrightarrow{1} D$，$A \xrightarrow{8} C$。

• 初始（直接边）：$d(A,B)=3$, $d(A,C)=8$, $d(B,C)=2$, $d(C,D)=1$, 其余 $\infty$
• $k=A$：检查是否通过 $A$ 中转更短。$B$ 到 $A$ 是 $\infty$，无改善
• $k=B$：$d(A,C) = \min(8, d(A,B)+d(B,C)) = \min(8, 3+2) = 5$。更新！ 通过 $B$ 中转更短
• $k=C$：$d(A,D) = \min(\infty, d(A,C)+d(C,D)) = \min(\infty, 5+1) = 6$。$d(B,D) = \min(\infty, 2+1) = 3$。更新！
• $k=D$：无进一步改善

复杂度

• 时间：$O(V^3)$（三重循环，无条件判断）
• 空间：$O(V^2)$（距离矩阵）
• 适用：全对最短路，尤其是稠密图。代码极其简洁（三行核心循环）

适用场景

Floyd-Warshall 最适合以下情况：

• 需要所有点对的最短距离（不只是从一个源点出发）
• 图的节点数不太大（$V \le 1000$ 左右）
• 可以处理负权边（但不能有负权环）
• 追求代码简洁——核心只有三行

启发式搜索：A* 算法

动机

Dijkstra 在每一步都向所有方向均匀扩展——它不知道目标在哪里。如果我们有关于目标位置的额外信息（如地理坐标），能不能让搜索更”有方向感”？

核心思想

A*（Hart, Nilsson & Raphael, 1968）在 Dijkstra 的基础上加了一个估价函数（heuristic function）$h(n)$，用来估计从节点 $n$ 到目标 $t$ 的剩余代价。优先队列不再按 $d[n]$ 排序，而是按

$f(n) = g(n) + h(n)$

其中 $g(n) = d[n]$（从起点到 $n$ 的已知最短距离），$h(n)$（从 $n$ 到目标的估计距离）。

Admissible Heuristic

$h(n)$ 必须满足可容纳性（admissibility）：$h(n) \le d(n, t)$，即估计值不超过真实值。这保证 A* 不会遗漏最短路径。

常见的可容纳启发式：

• 网格地图：曼哈顿距离（$|x_1 - x_2| + |y_1 - y_2|$，4 方向移动）或欧氏距离
• 道路网络：直线距离（great-circle distance）
• $h(n) = 0$：退化为 Dijkstra——没有方向信息

算法流程

AStar(G, s, t, h):
    g[s] = 0
    PQ = {s}, keyed by f(s) = g(s) + h(s)

    while PQ not empty:
        u = PQ.extract-min()   // 按 f(u) 选
        if u == t: return g[t]

        for each edge (u, v):
            tentative = g[u] + w(u, v)
            if tentative < g[v]:
                g[v] = tentative
                parent[v] = u
                PQ.insert-or-decrease(v, g[v] + h(v))

    return ∞  // 不可达

A* vs Dijkstra

维度	Dijkstra	A*
优先级	$g(n)$	$f(n) = g(n) + h(n)$
方向感	无（全向扩展）	有（朝目标聚焦）
探索节点数	更多	更少（好的 $h$ 下）
保证最优？	是	$h$ 可容纳时是
$h = 0$ 时	—	退化为 Dijkstra

A* 的优势不在于更低的最坏复杂度（最坏情况与 Dijkstra 相同），而在于实际探索的节点数大幅减少。在路径规划场景中，好的启发式能将搜索空间缩小几个数量级。

一致性（Consistency）

如果 $h$ 还满足一致性（consistency / monotonicity）：$h(u) \le w(u, v) + h(v)$（对所有边 $(u, v)$），那么 A* 保证每个节点只需处理一次（类似 Dijkstra）。可容纳但不一致的 $h$ 仍然保证最优，但可能需要多次处理同一节点。

欧氏距离和曼哈顿距离天然满足一致性（因为三角不等式）。

DAG 最短路径（回顾 Art. 3）

如果图是 DAG（有向无环图），最短路径有一个 $O(V + E)$ 的简洁解法——Art. 3 中我们已经建立了这个工具。

核心思想：先做拓扑排序，然后按拓扑序依次松弛每个节点的出边。因为 DAG 无环，拓扑序保证了每个节点在被处理时，所有指向它的前驱都已经处理完毕——所以只需要一遍就能得到所有最短距离。

DAG-Shortest-Path(G, s):
    topological-sort G
    d[s] = 0, 其余 ∞
    for each u in topological order:
        for each edge (u, v):
            Relax(u, v, w)

• 时间：$O(V + E)$——和 BFS 一样快！
• 条件：图必须是 DAG（无环）
• 优势：可以处理负权边（DAG 没有环，自然没有负权环）

DAG 最短路径在项目调度（PERT/CPM 关键路径分析）中特别常用——任务依赖关系天然形成 DAG。

复杂度对比与算法选型

复杂度对比表

算法	时间复杂度（最坏）	空间复杂度	负权边	负权环检测	适用场景
BFS	$O(V+E)$	$O(V)$	不适用	不适用	无权图
Dijkstra（二叉堆）	$O((V+E)\log V)$	$O(V)$	不支持	不支持	非负权单源
Bellman-Ford	$O(VE)$	$O(V)$	支持	支持	有负权单源
SPFA（BF 优化）	$O(VE)$（最坏）	$O(V)$	支持	支持	平均更快的 BF
Floyd-Warshall	$O(V^3)$	$O(V^2)$	支持	支持	全对最短路
A*	$O((V+E)\log V)$（最坏）	$O(V)$	不支持	不支持	有启发式的点到点
DAG 松弛	$O(V+E)$	$O(V)$	支持	不适用	DAG 单源

算法选型决策树

面对一个最短路径问题时，按以下决策树选择算法：

简单的经验法则：

1. 无权图？→ BFS，不要犹豫
2. DAG？→ 拓扑序松弛，$O(V+E)$
3. 有负权边？→ Bellman-Ford（顺便检测负权环）
4. 需要全对最短路？→ Floyd-Warshall（$V \le 1000$）或 $V$ 次 Dijkstra（稀疏图）
5. 有好的启发式？→ A*（点到点查询效率更高）
6. 以上都不是？→ Dijkstra（通用默认选择）

应用场景

导航与路线规划

Google Maps、Apple Maps、Waze 等导航应用的核心就是最短路径计算。道路网络是一个大规模加权图（节点 = 交叉口，边 = 路段，权重 = 时间或距离）。实际系统通常使用 A* 的变体（如 ALT 算法、Contraction Hierarchies）在千万级节点的图上实现毫秒级查询。

网络路由

互联网路由协议直接使用这些算法：

• OSPF（Open Shortest Path First）使用 Dijkstra 算法——每台路由器维护整个区域的拓扑图，用 Dijkstra 计算到所有目的地的最短路径
• BGP（Border Gateway Protocol）中路径选择的核心也是最短路径的变体
• RIP（Routing Information Protocol）本质上是分布式 Bellman-Ford——每台路由器只知道邻居信息，通过迭代交换距离向量收敛到最短路径

社交网络分析

社交网络中的”距离”衡量两个人之间的关系远近。“六度分隔”（Six Degrees of Separation）假说——任意两个人之间最多经过 6 个中间人——本质上是在社交图上做 BFS。而加权版本（如用互动频率作为边权的倒数）则需要 Dijkstra。全对最短路用于计算”介数中心性”（betweenness centrality），下一篇 Art. 7 将详细讨论。

关键路径分析（CPM/PERT）

项目管理中的关键路径法使用 DAG 最短路径（取负权后变成最长路径）来计算项目的最短完成时间。任务间的依赖关系形成 DAG，边权是任务持续时间，最长路径（critical path）决定了项目不可压缩的最短工期。

总结

本文建立了图上”距离”的完整工具箱：

• 松弛是所有最短路径算法的核心操作——检查三角不等式，违反就更新
• BFS：无权图 $O(V+E)$，逐层扩展保证最短跳数
• Dijkstra：非负权单源 $O((V+E)\log V)$，贪心选最近，一旦确定不再改变
• Bellman-Ford：有负权单源 $O(VE)$，反复松弛所有边 $|V|-1$ 轮，能检测负权环
• Floyd-Warshall：全对最短路 $O(V^3)$，DP 逐步增加可用中间节点
• A*：Dijkstra + 估价函数，$f(n) = g(n) + h(n)$，朝目标聚焦搜索
• DAG 松弛：$O(V+E)$，按拓扑序一遍搞定，可处理负权边

算法选择的关键在于识别约束：边权性质（非负/有负/无权）、问题类型（单源/全对/点对点）、图结构（DAG/一般图）、是否有启发式信息。正确的选择能带来数量级的性能差异。

有了”距离”这个度量工具，下一个自然的问题是：谁是图中最”重要”的节点？ 下一篇 Art. 7: 中心性 将回答这个问题——而其中最重要的”介数中心性”正是建立在本文的最短路径之上。

实现指引

算法	库	函数/方法
Dijkstra	NetworkX	nx.dijkstra_path(G, source, target, weight='weight')
Dijkstra（所有目标）	NetworkX	nx.single_source_dijkstra(G, source)
Bellman-Ford	NetworkX	nx.bellman_ford_path(G, source, target)
Bellman-Ford（负权环检测）	NetworkX	nx.negative_edge_cycle(G)
Floyd-Warshall	NetworkX	nx.floyd_warshall(G, weight='weight')
A*	NetworkX	nx.astar_path(G, source, target, heuristic)
Dijkstra（稀疏矩阵）	scipy	scipy.sparse.csgraph.dijkstra(graph, indices=source)
Bellman-Ford（稀疏矩阵）	scipy	scipy.sparse.csgraph.bellman_ford(graph, indices=source)
Floyd-Warshall（稀疏矩阵）	scipy	scipy.sparse.csgraph.floyd_warshall(graph)
Dijkstra / BF	igraph	g.distances(source, weights='weight')