最短路径算法

这一节整理图中的最短路径问题，包括无权图最短路、Dijkstra 算法、负边权图、DAG 上的最短路、AOE 网络与关键路径，以及全源最短路径问题。

这页的目标不是只背结论，而是能看懂算法为什么这样做。最短路径算法表面上有很多名字，但核心动作其实很统一：不断尝试用一条更短的路线更新某个顶点的当前距离。

1. 最短路径问题

给定一个有向图：

G = (V, E)

以及边上的代价函数 c(e)，其中 e ∈ E(G)。

一条从源点到终点的路径 P 的长度定义为路径上所有边权之和：

\[ \sum_{e_i \subset P} c(e_i) \]

这也称为带权路径长度（weighted path length）。

如果所有边都没有权重，可以把每条边看成权重为 1。
这时“最短”指的是经过的边数最少；如果有边权，“最短”指的是边权总和最小。

例如：

s -> a -> t      长度 = 2 + 3 = 5
s -> b -> t      长度 = 1 + 10 = 11

虽然两条路径都走了两条边，但第一条路径的带权长度更短。

2. 单源最短路径

单源最短路径问题（Single-Source Shortest-Path Problem）是：

给定一个带权图 G = (V, E) 和一个指定源点 s，求从 s 到图中每一个其他顶点的最短带权路径。

需要注意：

如果图中存在负权环（negative-cost cycle），最短路径可能没有定义，因为路径可以不断绕环让总代价变得更小。
如果不存在负权环，通常把从 s 到 s 的最短路径定义为 0。

为什么负权环会让最短路失去意义

假设从 s 可以走到某个环，并且这个环总权重为 -5。
那么你绕这个环一圈，路径长度减少 5；绕十圈，路径长度减少 50。这样路径长度可以无限变小，不存在一个“最小值”。

s -> ... -> a -> b -> c -> a -> ... -> t
              环总权重 = -5

所以讨论最短路径时，真正危险的不是“有负边”，而是“有可以到达的负权环”。

3. 表结构 Table

几种最短路径算法都会用到类似的表结构。对每个顶点 vi，维护：

Table[i].Dist   // 从源点 s 到 vi 的当前最短距离估计
Table[i].Known  // vi 是否已经被确认
Table[i].Path   // 最短路径上 vi 的前驱顶点，用来还原路径

初始化时：

源点 s 的 Dist 为 0。
其他顶点的 Dist 为 Infinity。
Known 初始为 false。
Path 初始为空或 0，具体取决于代码约定。

这张表可以理解成算法的“草稿本”：

Dist 是目前为止发现的最好答案，但不一定已经最终确定。
Known 表示这个点的答案已经确定，后面不会再变。
Path 用来记住最短路从哪里走过来，最后倒着恢复路径。

4. 共同核心：松弛操作

最短路径算法里最重要的动作叫松弛（relaxation）。

假设现在已经知道从源点 s 到 V 的距离是 Dist[V]，并且图中有一条边：

V -> W

边权为 Cvw。
那么经过 V 到达 W 的路径长度就是：

Dist[V] + Cvw

如果这个值比当前记录的 Dist[W] 更小，就说明我们找到了一条到 W 的更短路径，于是更新：

if (Dist[V] + Cvw < Dist[W]) {
    Dist[W] = Dist[V] + Cvw;
    Path[W] = V;
}

这就是松弛。

松弛的直觉

可以把 Dist[W] 想成目前写在表里的“到 W 的最好报价”。
现在从 V 这边又递来一个新报价 Dist[V] + Cvw：

如果新报价更贵，不理它。
如果新报价更便宜，就覆盖原来的报价，并记录“我是从 V 过来的”。

几乎所有最短路径算法的区别都在于：按照什么顺序拿顶点出来松弛它的边。

算法	拿点顺序
BFS	按离源点的边数一层一层拿
Dijkstra	每次拿当前 `Dist` 最小的未知顶点
负边权队列算法	谁的距离刚变小，就把谁重新拿出来
DAG 最短路	按拓扑序拿

5. 无权图最短路径

如果图是无权图，可以把每条边的权重都看成 1。
此时最短路径就是边数最少的路径。

核心思想是按距离分层：

0: 源点
1: 距离源点 1 条边的顶点
2: 距离源点 2 条边的顶点
3: 距离源点 3 条边的顶点
...

这本质上就是广度优先搜索（Breadth-First Search, BFS）。

为什么 BFS 能得到无权最短路

BFS 的队列保证了一个很重要的性质：先出队的顶点，距离一定不会比后出队的顶点更大。

从源点开始：

源点距离是 0。
源点的所有邻接点距离是 1。
距离为 1 的点再扩展出去，第一次发现的新点距离是 2。
继续这样一层一层扩展。

因为所有边的长度都一样，所以第一次发现某个顶点时，走到它的路径一定是边数最少的路径。

举个小例子：

s -> a -> c
s -> b -> c
s -> d

从 s 开始：

步骤	队列	新发现	距离变化
初始	`s`	`s`	`Dist[s] = 0`
处理 `s`	`a, b, d`	`a, b, d`	它们距离都是 `1`
处理 `a`	`b, d, c`	`c`	`Dist[c] = 2`
处理 `b`	`d, c`	无	`c` 已经被发现，不再更新

当 c 第一次被发现时，它的距离就是 2。后面即使从 b 也能到 c，距离仍然是 2，不会更短。

6. 朴素无权最短路

课件中的朴素版本按 CurrDist 从小到大扫描，每一轮找出当前距离为 CurrDist 且还没有被确认的顶点。

void Unweighted(Table T) {
    int CurrDist;
    Vertex V, W;

    for (CurrDist = 0; CurrDist < NumVertex; CurrDist++) {
        for (each vertex V) {
            if (!T[V].Known && T[V].Dist == CurrDist) {
                T[V].Known = true;

                for (each W adjacent to V) {
                    if (T[W].Dist == Infinity) {
                        T[W].Dist = CurrDist + 1;
                        T[W].Path = V;
                    }
                }
            }
        }
    }
}

每一层都要扫描所有顶点，时间复杂度为：

T = O(|V|^2)

这个版本的问题是：为了找“当前距离等于 CurrDist 的点”，每一轮都要重新扫一遍所有顶点。
它能表达 BFS 分层思想，但实现上不够高效。

7. 队列优化：BFS

改进方法是用队列保存已经发现但还没有展开的顶点。

void Unweighted(Table T) {
    Queue Q;
    Vertex V, W;

    Q = CreateQueue(NumVertex);
    MakeEmpty(Q);

    Enqueue(S, Q);  /* enqueue the source vertex */

    while (!IsEmpty(Q)) {
        V = Dequeue(Q);
        T[V].Known = true;  /* not really necessary */

        for (each W adjacent to V) {
            if (T[W].Dist == Infinity) {
                T[W].Dist = T[V].Dist + 1;
                T[W].Path = V;
                Enqueue(W, Q);
            }
        }
    }

    DisposeQueue(Q);
}

每个顶点最多入队一次，每条边最多检查一次，所以：

T = O(|V| + |E|)

在无权图中，这就是最自然的单源最短路径算法。

为什么 `Known` 在 BFS 中不是必须的

代码里写了：

T[V].Known = true;  /* not really necessary */

原因是 BFS 用 Dist[W] == Infinity 判断一个顶点是否第一次被发现。
只要一个顶点已经有了距离，它就不会再次入队。因此 Known 不是核心条件，只是帮助理解“已经处理过”。

8. Dijkstra 算法

Dijkstra 算法用于边权非负的带权最短路径问题。

设：

S = { 源点 s，以及最短路径已经确定的顶点 }

对于任意 u ∉ S，distance[u] 表示从 s 出发，只经过 S 中顶点作为中间点，到达 u 的当前最短距离。

算法每一步都选择：

distance[u] = min { distance[w] | w ∉ S }

也就是当前未知顶点中距离估计最小的顶点。
如果最小者不唯一，任选一个即可。

这是一个贪心算法。它正确的关键依赖是：边权不能为负。
一旦当前最小距离顶点被选中，它的最短路就不会再被后续路径降低。

Dijkstra 和 BFS 的关系

BFS 可以看成所有边权都等于 1 时的特殊最短路算法。
Dijkstra 则是在边权不完全相同，但都非负时使用。

BFS 的“层数”就是距离：

0, 1, 2, 3, ...

Dijkstra 的“层数”变成了当前最小的 Dist：

0, 2, 3, 5, 8, ...

所以 Dijkstra 的核心问题是：每次怎么快速找到当前 Dist 最小的未知顶点。

一个小例子

设源点为 s：

s --2--> a
s --5--> b
a --1--> b
a --4--> c
b --2--> c

初始化：

顶点	Dist	Path	Known
s	0	-	false
a	∞	-	false
b	∞	-	false
c	∞	-	false

第 1 步，选择 Dist 最小的未知顶点 s，松弛 s 的出边：

顶点	Dist	Path	说明
a	2	s	通过 `s -> a`
b	5	s	通过 `s -> b`
c	∞	-	还没发现

第 2 步，未知顶点里 a 最小，选 a，松弛 a 的出边：

到 b 的新距离 = Dist[a] + 1 = 2 + 1 = 3

因为 3 < 5，所以更新 b：

顶点	Dist	Path
a	2	s
b	3	a
c	6	a

第 3 步，未知顶点里 b 最小，选 b，松弛 b -> c：

到 c 的新距离 = Dist[b] + 2 = 3 + 2 = 5

因为 5 < 6，所以更新 c：

顶点	Dist	Path
b	3	a
c	5	b

第 4 步，选 c，结束。
最终从 s 到 c 的最短路径通过 Path 倒推：

c <- b <- a <- s

反过来就是：

s -> a -> b -> c

长度为：

2 + 1 + 2 = 5

9. Dijkstra 伪代码

课件中的伪代码可以整理为：

void Dijkstra(Table T) {
    Vertex V, W;

    for (;;) {
        V = smallest unknown distance vertex;

        if (V == NotAVertex) {
            break;
        }

        T[V].Known = true;

        for (each W adjacent to V) {
            if (!T[W].Known) {
                if (T[V].Dist + Cvw < T[W].Dist) {
                    Decrease(T[W].Dist to T[V].Dist + Cvw);
                    T[W].Path = V;
                }
            }
        }
    }
}

其中 Cvw 表示边 <V, W> 的权重。

这段代码中最重要的是两层动作：

外层：选一个当前 Dist 最小的未知顶点 V，把它变成 Known。
内层：用 V 去松弛所有邻接点 W。

Known = true 的含义很强：它不是“访问过”，而是“最短路径已经确定”。
这是 Dijkstra 和普通搜索最大的区别。

路径还原

如果 T[W].Path = V，表示当前从源点到 W 的最短路径中，W 的前驱是 V。
从目标点不断沿 Path 往回走，就可以还原完整路径。

例如：

Path[v7] = v4
Path[v4] = v1
Path[v1] = s

则从 s 到 v7 的路径为：

s -> v1 -> v4 -> v7

10. Dijkstra 的复杂度

Dijkstra 的性能主要取决于如何找到“未知顶点中距离最小的顶点”。

实现一：直接扫描

每次都扫描整张表：

V = smallest unknown distance vertex

单次查找 O(|V|)，总复杂度为：

T = O(|V|^2 + |E|)

通常简写为：

O(|V|^2)

这种实现适合稠密图。

实现二：优先队列

用优先队列维护当前距离：

DeleteMin 取出当前距离最小的顶点，复杂度 O(log |V|)。
当某个顶点的距离变小时，可以执行 DecreaseKey，复杂度 O(log |V|)。

复杂度为：

T = O(|V| log |V| + |E| log |V|)

通常可写成：

O(|E| log |V|)

这种实现适合稀疏图。

如果不支持 DecreaseKey，也可以把更新后的新距离重新插入优先队列。
这时需要不断 DeleteMin，直到取出一个还未知的顶点。复杂度仍可做到：

O(|E| log |V|)

但可能需要更多空间，最多可能有 |E| 个队列元素。

课件还提到可以用 Pairing Heap 或 Fibonacci Heap 做进一步优化。

稠密图和稀疏图怎么选

如果一个图有很多边，接近完全图，就是稠密图。此时 |E| 可能接近 |V|^2，直接扫描的 O(|V|^2) 很合适。

如果一个图边数远少于 |V|^2，就是稀疏图。此时用优先队列通常更好，因为它避免了反复扫描大量没有边或不相关的顶点。

可以粗略记成：

稠密图：邻接矩阵 + 直接扫描 Dijkstra
稀疏图：邻接表 + 优先队列 Dijkstra

11. Dijkstra 的限制

Dijkstra 不能处理负边权。

原因是：它一旦把某个顶点加入 S，就认为该顶点的最短距离已经确定。
如果存在负边，后面可能通过某条负边找到更短路径，从而推翻之前的结论。

一个常见错误想法是：

给每条边都加上一个常数，让所有边权都变成非负，然后再跑 Dijkstra。

这个做法不正确。
因为不同路径包含的边数可能不同，给每条边加同一个常数会改变不同路径之间的相对大小。

例如：

路径 A: 1 条边，原长度 5
路径 B: 3 条边，原长度 4

如果每条边都加 2：

路径 A: 5 + 2 = 7
路径 B: 4 + 3 * 2 = 10

原来更短的路径 B 反而变得更长，最短路径结构被改变了。

负边为什么会破坏 Dijkstra

看这个例子：

s --2--> a
s --5--> b
b --(-4)--> a

Dijkstra 从 s 开始，先得到：

Dist[a] = 2
Dist[b] = 5

因为 a 的距离最小，所以 Dijkstra 会先把 a 确认为 Known。
但实际上存在路径：

s -> b -> a

长度为：

5 + (-4) = 1

这比 2 更短。问题在于，更短路径要经过一个当时距离更大的顶点 b，而负边会把后面的距离“拉低”。这正好违背了 Dijkstra 的贪心前提。

12. 含负边权的图

如果图中有负边权，但没有负权环，可以使用一种基于队列反复松弛的算法。

课件中的伪代码：

void WeightedNegative(Table T) {
    Queue Q;
    Vertex V, W;

    Q = CreateQueue(NumVertex);
    MakeEmpty(Q);

    Enqueue(S, Q);

    while (!IsEmpty(Q)) {
        V = Dequeue(Q);

        for (each W adjacent to V) {
            if (T[V].Dist + Cvw < T[W].Dist) {
                T[W].Dist = T[V].Dist + Cvw;
                T[W].Path = V;

                if (W is not already in Q) {
                    Enqueue(W, Q);
                }
            }
        }
    }

    DisposeQueue(Q);
}

这个算法的直觉是：只要某个顶点的距离被更新，就把它放回队列，让它继续尝试更新自己的邻接点。

复杂度为：

T = O(|V| * |E|)

如果存在负权环，算法可能不断更新距离，导致无法停止。
因此需要额外机制检测负权环。

它和 Dijkstra 的差别

Dijkstra 是“一旦选中就不再反悔”。
负边权算法则允许反复修正：如果某个点的距离变小了，就把它重新放入队列，让它继续影响后面的点。

所以它更宽容，但代价是更慢。
如果一个顶点的距离被更新很多次，它就可能多次入队。

13. DAG 上的最短路径

如果图是有向无环图（DAG），可以按照拓扑序处理顶点。

原因是：当一个顶点按拓扑序被处理时，它不会再收到来自未知顶点的入边，因此它的最短距离不会再被降低。

流程：

对 DAG 做拓扑排序。
按拓扑序依次处理顶点。
对每条出边执行松弛操作。

复杂度为：

T = O(|V| + |E|)

这种方法不需要优先队列，并且可以处理 DAG 中的负边权，只要图没有环。

为什么 DAG 可以用拓扑序

拓扑序保证所有边都从前指向后。
当我们处理某个顶点 V 时，所有能影响 V 的前驱都已经处理完了，所以 Dist[V] 已经不会再被更早的路径更新。

这个逻辑和 Dijkstra 不一样：

Dijkstra 靠“边权非负”保证当前最小值不会被推翻。
DAG 最短路靠“没有环 + 拓扑序”保证前驱已经全部处理完。

因此 DAG 最短路即使有负边也可以工作，只要仍然无环。

14. AOE 网络

AOE Network 是 Activity On Edge Network，用于项目调度。

和 AOV 网络不同：

AOV 网络中，顶点表示活动，边表示先后关系。
AOE 网络中，边表示活动，顶点表示事件或状态。

如果活动 ai 是一条边：

ai = <v, w>

那么：

边 <v, w> 表示活动 ai。
边权 Cvw 表示活动持续时间。
顶点 w 可以理解为活动 ai 完成所到达的事件。

AOV 和 AOE 的区别

这两个名字很像，很容易混：

网络	顶点表示	边表示	常见用途
AOV	活动	活动之间的先后关系	拓扑排序
AOE	事件	活动及其持续时间	项目工期、关键路径

在 AOE 里，活动是有持续时间的，所以持续时间自然放在边上。

15. EC 与 LC

AOE 网络中常用两个时间：

EC[j]：顶点 vj 的最早完成时间（earliest completion time）。
LC[j]：顶点 vj 的最晚完成时间（latest completion time）。

EC 的计算

从起点开始，按照拓扑序向后计算。
对于任意边 <v, w>：

\[ EC[w] = \max_{(v,w) \in E}\{EC[v] + C_{v,w}\} \]

含义是：一个事件要等所有前置活动都完成后才能发生，所以取最大值。

LC 的计算

从终点开始，按照逆拓扑序向前计算。
对于任意边 <v, w>：

\[ LC[v] = \min_{(v,w) \in E}\{LC[w] - C_{v,w}\} \]

含义是：为了不推迟整个项目，前面的事件最晚必须在某些后续活动开始前完成，所以取最小值。

EC/LC 小例子

看一个简单项目：

0 --3--> 1 --4--> 3
0 --2--> 2 --6--> 3

从 0 到 3 有两条路线：

0 -> 1 -> 3    总时间 = 3 + 4 = 7
0 -> 2 -> 3    总时间 = 2 + 6 = 8

先算 EC：

EC[0] = 0
EC[1] = EC[0] + 3 = 3
EC[2] = EC[0] + 2 = 2
EC[3] = max(EC[1] + 4, EC[2] + 6)
      = max(7, 8)
      = 8

所以整个项目最早完成时间是 8。

再算 LC，终点的 LC 等于项目完成时间：

LC[3] = 8
LC[1] = LC[3] - 4 = 4
LC[2] = LC[3] - 6 = 2
LC[0] = min(LC[1] - 3, LC[2] - 2)
      = min(1, 0)
      = 0

这里 LC[1] = 4 表示事件 1 最晚可以在时间 4 发生，再晚就会影响项目完成时间。
但 EC[1] = 3，说明事件 1 最早时间是 3，它有 1 个时间单位的余量。

16. Slack Time 与关键路径

一条活动边 <v, w> 的松弛时间（slack time）为：

\[ Slack(v,w) = LC[w] - EC[v] - C_{v,w} \]

如果一条边的 slack time 为 0，说明这条活动没有可延迟空间。

关键路径（Critical Path）是全部由零松弛边组成的路径。

关键路径的意义：

关键路径长度就是整个项目的最短完成时间。
关键路径上的任意活动延迟，都会导致整个项目延迟。
非关键活动只要延迟不超过 slack time，就不会影响总工期。

这套方法称为 CPM（Critical Path Method）。

用上面的例子算 Slack

对边 0 -> 1：

Slack(0,1) = LC[1] - EC[0] - 3
           = 4 - 0 - 3
           = 1

所以活动 0 -> 1 可以延迟 1 个时间单位。

对边 0 -> 2：

Slack(0,2) = LC[2] - EC[0] - 2
           = 2 - 0 - 2
           = 0

对边 2 -> 3：

Slack(2,3) = LC[3] - EC[2] - 6
           = 8 - 2 - 6
           = 0

因此关键路径是：

0 -> 2 -> 3

它的总长度是 8，正好等于项目最早完成时间。

17. 全源最短路径

全源最短路径问题（All-Pairs Shortest Path Problem）是：

对所有顶点对 vi 和 vj，其中 i ≠ j，求它们之间的最短路径。

课件给出两类方法。

方法一：单源算法重复执行

对每个顶点都跑一次单源最短路径算法。

如果使用简单实现，复杂度可以达到：

T = O(|V|^3)

这种方法在稀疏图上通常比较快。

方法二：专门的全源算法

课件提到第 10 章会给出一个 O(|V|^3) 的算法。
这类算法在稠密图上通常更有优势。

典型代表是 Floyd-Warshall 算法。

选择方法时可以这样理解：

如果图很稀疏，而且已经有好用的单源算法，可以从每个顶点跑一遍。
如果图很稠密，矩阵式的全源算法通常更直接。

18. 实验提示

这份课件最后提到 Laboratory Project 3：

Normal: Dijkstra Sequence
Hard: Transportation Hub

其中 Dijkstra Sequence 通常考察的是：给定一个顶点序列，判断它是否可能是 Dijkstra 算法中顶点被确定的顺序。

判断时要记住 Dijkstra 的核心规则：

每一步必须选择当前未知顶点中 Dist 最小的顶点。
如果有多个顶点并列最小，任选一个都合法。
每选中一个顶点，就用它的出边更新相邻顶点距离。

Dijkstra Sequence 怎么想

判断一个序列是否合法时，不是看它像不像 BFS，也不是看顶点编号大小，而是模拟 Dijkstra 的表。

每一步检查：

当前序列给出的顶点 V 是否还是 unknown。
V 的 Dist 是否等于所有 unknown 顶点里的最小值。
如果是，就接受它，并用 V 的出边做松弛。
如果不是，就说明这个序列不可能是 Dijkstra 的选择顺序。

并列最小时要特别小心。
如果此时有两个 unknown 顶点的 Dist 都是 5，序列先选其中任意一个都合法。

19. 一页速记

问题	算法	条件	复杂度
无权单源最短路	BFS	每条边权为 `1`	`O(\|V\| + \|E\|)`
非负权单源最短路	Dijkstra 直接扫描	边权非负，适合稠密图	`O(\|V\|^2 + \|E\|)`
非负权单源最短路	Dijkstra + 优先队列	边权非负，适合稀疏图	`O(\|E\| log \|V\|)`
含负边单源最短路	队列反复松弛	不能有负权环	`O(\|V\| * \|E\|)`
DAG 最短路	拓扑序 + 松弛	有向无环图	`O(\|V\| + \|E\|)`
AOE/关键路径	拓扑序计算 EC、逆拓扑序计算 LC	项目调度网络	`O(\|V\| + \|E\|)`
全源最短路	重复单源算法	适合稀疏图	常见为 `O(\|V\|^3)`
全源最短路	Floyd-Warshall 类算法	适合稠密图	`O(\|V\|^3)`

20. 易错点

Dijkstra 不能处理负边权。
给所有边加同一个常数不能把负边权问题变成等价的非负边权问题。
负权环会让最短路径失去意义。
无权图最短路径应优先想到 BFS。
DAG 最短路按拓扑序做，不需要优先队列。
AOE 网络中边表示活动，AOV 网络中顶点表示活动。
关键路径由 slack = 0 的活动组成。
Dijkstra Sequence 中，并列最小距离的顶点可以有多个合法选择。

最短路径算法

1. 最短路径问题

2. 单源最短路径

为什么负权环会让最短路失去意义

3. 表结构 Table

4. 共同核心：松弛操作

松弛的直觉

5. 无权图最短路径

为什么 BFS 能得到无权最短路

6. 朴素无权最短路

7. 队列优化：BFS

为什么 Known 在 BFS 中不是必须的

8. Dijkstra 算法

Dijkstra 和 BFS 的关系

一个小例子

9. Dijkstra 伪代码

路径还原

10. Dijkstra 的复杂度

实现一：直接扫描

实现二：优先队列

稠密图和稀疏图怎么选

11. Dijkstra 的限制

负边为什么会破坏 Dijkstra

12. 含负边权的图

它和 Dijkstra 的差别

13. DAG 上的最短路径

为什么 DAG 可以用拓扑序

14. AOE 网络

AOV 和 AOE 的区别

15. EC 与 LC

EC 的计算

LC 的计算

EC/LC 小例子

16. Slack Time 与关键路径

用上面的例子算 Slack

17. 全源最短路径

方法一：单源算法重复执行

方法二：专门的全源算法

18. 实验提示

Dijkstra Sequence 怎么想

19. 一页速记

20. 易错点

为什么 `Known` 在 BFS 中不是必须的