第 117 章 图论进阶：k 短路与关键路径¶
配套例题：BISHI109 邮递员送信、BISHI108 最优乘车 来源：S4
模板.docx/「图论 → 最短路 → 2.k 短路（暂时没有）」「图论 → 5.关键路径（好像不太重要）」「最短路 → 4.SPFA（路径条数）」「最短路 → 5.floyd 判最小环」（sources/03-pascal-template/模板.md第 74、76、84 行的清单，第 3062 行「SPFA（路径条数）」、第 3098 行「Floyd 判最小环」两份源码） 前置：91-最短路、93-拓扑排序与二分图、35-优先队列与堆
117.0 这一章为什么存在¶
S4 模板.docx 的图论目录里有两条特别的记录：
括号里的话都是原文。这是整份模板文档里唯一两个「作者自己承认没写完」的条目：
| 条目 | 作者的态度 | 实际情况 |
|---|---|---|
| k 短路 | 「暂时没有」——想写但没写 | NOIP/省选常考，A* 做法只比 Dijkstra 多 5 行 |
| 关键路径 | 「好像不太重要」 | 数据结构教材的必考内容，工程上就是项目管理的 PERT/CPM |
于是这一章要做的事很明确：把 S4 留下的两个空格填上。
而牛客题单里同样没有这两类题（题单里的图论题止于 Dijkstra / MST / 拓扑排序）。 最接近的是两道建模题：
| 例题 | 与本章的关系 |
|---|---|
| BISHI109 邮递员送信 | 「正图 + 反图各跑一次 Dijkstra」——反图最短路正是 k 短路 A* 的估价函数 |
| BISHI108 最优乘车 | 「拆点 + 虚拟链 + 0-1 BFS」——虚拟链就是一条 AOE 链，与关键路径同源 |
这一章的定位：
| 目标 | 说明 |
|---|---|
| 补上 S4 的两个空缺 | A* 求 k 短路、AOE 网与关键路径 |
| 在 DAG 上重做「最长路」与「最短路计数」 | 91 章 给的是 SPFA 版（要两个数组、要判在不在队列）；DAG 上一遍拓扑序就够了，还不用取模判重 |
| 收束 Floyd 判最小环 | 91 章已给实现，这里补「为什么无向图和有向图的最小环做法不同」 |
| 给出诚实的可行性判断 | A* 求 k 短路的堆会爆，\(n, k\) 到多少该放弃 |
先给结论：
A* 求 k 短路在 Python 里的实用上限约为 \(n \le 5\times10^3\)、\(m \le 10^5\)、\(k \le 10^3\) （堆里最多 \(O(m + nk)\) 个元素，\(nk\) 是真正的瓶颈）。 关键路径是纯 \(O(n+m)\) 的拓扑序 DP，\(n = 10^6\) 也没问题—— 这两者在 Python 里的地位是天差地别的。
117.1 A*：把「已走」和「还要走」分开¶
Dijkstra 按 \(g(u)\)（起点到 \(u\) 的实际距离）排序出队； A* 按 \(f(u) = g(u) + h(u)\) 排序，其中 \(h(u)\) 是「\(u\) 到终点的距离估计」。
| 记号 | 含义 |
|---|---|
| \(g(u)\) | 从起点走到 \(u\) 已经花的代价（已知的过去） |
| \(h(u)\) | 从 \(u\) 走到终点还要花的代价的估计（猜测的未来） |
| \(f(u) = g + h\) | 经过 \(u\) 的整条路径的代价估计 |
| \(h\) 的性质 | 名字 | 后果 |
|---|---|---|
| \(h(u) \le\) 真实剩余距离 | 可采纳（admissible） | A* 保证找到最优解 |
| $h(u) = $ 真实剩余距离 | 完美估价 | A* 只走最短路上的点，一步不多 |
| \(h(u) >\) 真实剩余距离 | 不可采纳 | ❌ 可能找到非最优解 |
| \(h(u) = 0\) | 退化 | A* \(\equiv\) Dijkstra |
A* 不是新算法，是「带偏见的 Dijkstra」。 偏见（\(h\)）越准，扩展的点越少；偏见不能过头（不能高估），否则会剪掉最优解。 同一个思想在搜索里叫 IDA*（见 115 章）， 区别只是「优先队列」换成了「迭代加深」。
k 短路问题里的完美估价函数¶
求 \(s \to t\) 的第 \(k\) 短路时，有一个几乎免费的完美估价函数：
怎么求？在反图上从 \(t\) 跑一次 Dijkstra。 这正是 BISHI109 用的那一招：
在反图上从 \(t\) 出发的单源最短路，就是原图上「所有点到 \(t\)」的最短路。 一次 Dijkstra 顶 \(n\) 次。见 91-最短路 · 建图技巧。
于是 A* 的 \(h\) 是精确值而不是估计值，\(f = g + h\) 就是「经过 \(u\) 的最优完整路径长度」。
117.2 A* 求 k 短路¶
算法（只有 5 行是新的）：
1. 反图上从 t 跑 Dijkstra，得到 h[]
2. 优先队列按 f = g + h 排序，初始塞入 (h[s], 0, s)
3. 每次弹出 f 最小的 (f, g, u)：
cnt[u] += 1
若 u == t 且 cnt[t] == k -> 答案就是 g，结束
若 cnt[u] > k -> 丢弃（同一个点入队 k 次以上没有意义）
否则把所有出边 (u -> v) 以 (g + w + h[v], g + w, v) 入队
正确性的两个支柱：
| 支柱 | 说明 |
|---|---|
| 弹出顺序即 \(f\) 的升序 | 因为 \(h\) 是精确的，\(f\) 就是完整路径长度 → 第 \(i\) 次弹出 \(t\) 就是第 \(i\) 短路 |
cnt[u] > k 可以剪 |
一条 \(s\to t\) 的路径经过 \(u\) 时，\(u\) 前面那一段是 \(s\to u\) 的某条路径；第 \(k\) 短的 \(s\to t\) 路径最多用到 \(s \to u\) 的第 \(k\) 短路 |
# [片段]
import sys
from heapq import heappush, heappop
def build_csr(n, us, vs, ws):
"""把边表压成 CSR（前向星）。返回 (start, to, wt)，点编号 1..n。"""
m = len(us)
deg = [0] * (n + 2) # 先数出度，才知道每个点该占哪一段
for u in us:
deg[u] += 1
start = [0] * (n + 2)
acc = 0
for i in range(1, n + 1):
start[i] = acc # 出度的前缀和（不含自己）= 该点的起始下标
acc += deg[i]
start[n + 1] = acc # 哨兵，使 start[u+1] 对 u = n 也有定义
pos = start[:] # pos[u] 是 u 的下一个空槽
to = [0] * acc
wt = [0] * acc
for i in range(m):
u = us[i]
k = pos[u]
to[k] = vs[i]; wt[k] = ws[i] # 终点与边权放同一个下标，遍历时一起取
pos[u] = k + 1
return start, to, wt
def dijkstra(n, start, to, wt, src):
"""堆优化 Dijkstra + 懒删除。heapq 没有 decrease-key，这是唯一正确姿势。"""
INF = float('inf')
dist = [INF] * (n + 1) # INF 兼作「还没到达过」的标记
dist[src] = 0
h = [(0, src)] # 堆里存 (当前距离, 点)，按距离排序
while h:
d, u = heappop(h)
if d > dist[u]:
continue # 这条记录已被更短的取代，是过期副本，跳过
for i in range(start[u], start[u + 1]):
v = to[i]
nd = d + wt[i]
if nd < dist[v]: # 松弛成功才入堆，堆里因此可能有同一点的多份记录
dist[v] = nd
heappush(h, (nd, v))
return dist
def kth_shortest(n, us, vs, ws, s, t, k):
"""A* 求 s->t 的第 k 短路（**允许重复经过点与边**）。不存在返回 -1。
h[u] = u 到 t 的最短路（在反图上一次 Dijkstra 求得）—— 这是**精确**估价，
所以弹出顺序就是路径长度的升序，第 k 次弹出 t 即答案。
复杂度 O(m log m + nk log(nk))。堆里最多 O(m + nk) 个元素。
"""
fs, ft, fw = build_csr(n, us, vs, ws) # 正图
rs, rt, rw = build_csr(n, vs, us, ws) # ★ 反图：us 与 vs 交换
h = dijkstra(n, rs, rt, rw, t) # 估价函数
INF = float('inf')
if h[s] == INF:
return -1 # s 根本到不了 t
cnt = [0] * (n + 1) # cnt[u]：u 已被弹出几次
pq = [(h[s], 0, s)] # (f, g, u)；起点还没走路，g = 0
while pq:
f, g, u = heappop(pq) # h 精确，所以 f 就是完整路径长度
cnt[u] += 1 # 第 i 次弹出 u = s 到 u 的第 i 短路
if u == t and cnt[t] == k:
return g # 返回 g（真实长度）而不是 f，此时 h[t] = 0
if cnt[u] > k:
continue # ★ 每个点最多有用地扩展 k 次
for i in range(fs[u], fs[u + 1]):
v = ft[i]
if h[v] == INF:
continue # v 到不了 t，这条边没意义
ng = g + fw[i] # 新的已走代价
heappush(pq, (ng + h[v], ng, v)) # 排序键是 ng + h[v]，g 一并带上备用
return -1 # 堆空了还没弹出 t 第 k 次 -> 路径不足 k 条
自测（与「按长度枚举所有 walk」的暴力对拍 200 组随机小图，全部一致）：
| 图 | 询问 | 结果 |
|---|---|---|
| \(1\to2\)（权 1）、\(2\to1\)（权 1）、\(2\to3\)（权 1） | \(1\to3\) 的第 1 / 2 / 3 短路 | 2 / 4 / 6（可以来回绕） |
| 单条链 \(1\to2\to3\) | 第 2 短路 | \(-1\)（只有一条路径） |
变体：不允许重复经过点¶
上面的模板求的是「walk」（可以绕圈）的第 \(k\) 短，这是竞赛里 k 短路的默认定义 （洛谷 P2483 / POJ 2449 都是这个定义）。
如果题目要求「简单路径（不重复经过点）的第 \(k\) 短」， 问题立刻变成 NP 困难级别的难题，标准做法是 Yen 算法（\(O(kn(m + n\log n))\)）：
Yen 算法：
A[1] = 最短路
for i = 2..k:
对 A[i-1] 上每个「分叉点」，禁用已用过的那条边，重跑一次最短路
把得到的候选路径放进一个候选集 B
A[i] = B 中最短的那条
⚠️ 看到「k 短路」先确认定义： - 「路径可以重复经过点」→ A* 模板，\(O(nk\log)\)，能过； - 「必须是简单路径」→ Yen，要跑 \(O(k \cdot n)\) 次 Dijkstra，Python 基本没戏。
竞赛里 95% 是前者。判据是题面有没有「不重复」「简单路径」这几个字。
k 短路的做法对照¶
| 做法 | 复杂度 | Python 判断 |
|---|---|---|
| A* + 反图 Dijkstra | \(O(m\log m + nk\log(nk))\) | ✅ 首选，\(nk \le 10^6\) 可行 |
| 每个点维护「前 \(k\) 短」数组 + Dijkstra 变形 | \(O(mk\log)\) | ⚠️ 常数比 A* 大 |
| 可持久化可并堆（左偏树） | \(O(m\log m + k\log k)\) | ❌ Python 不现实（理论最优但常数巨大） |
| Yen（简单路径版） | \(O(kn(m+n\log n))\) | ❌ |
| 暴力 BFS 枚举所有路径 | 指数 | ❌ |
A* 的 \(nk\) 是怎么来的：每个点最多被有效弹出 \(k\) 次， 每次弹出会把它的出边全部入队 → 入队总量 \(O(mk)\) 上界、实际约 \(O(nk)\) 量级。 堆里的元素个数就是内存瓶颈：\(nk = 10^6\) 时堆里 \(10^6\) 个三元组约 100 MB。
117.3 AOE 网与关键路径¶
两种网络：AOV 与 AOE¶
| 名字 | 全称 | 顶点表示 | 边表示 | 解决什么 |
|---|---|---|---|---|
| AOV 网 | Activity On Vertex | 活动 | 先后依赖 | 可行的执行顺序 → 拓扑排序 |
| AOE 网 | Activity On Edge | 事件（里程碑） | 活动（带耗时） | 整个工程的最短工期 → 关键路径 |
AOE 网的顶点是「事件」而不是「任务」，这是最容易搞混的一点。 「顶点 \(v\) 发生」意味着「所有指向 \(v\) 的活动都已完成，所有从 \(v\) 出发的活动都可以开始」。 所以顶点是时刻，边是工序。
AOE 网必须是 DAG（有环意味着工序互相等待，工程永远做不完）。
四个量¶
设活动 \(a = (u \to v)\)，耗时 \(w\)：
| 量 | 记号 | 含义 | 递推 |
|---|---|---|---|
| 事件最早发生时间 | \(ve[v]\) | 所有前驱活动都完成的最早时刻 | \(ve[v] = \max_{(u\to v)}\{ve[u] + w\}\)，按拓扑序正推 |
| 事件最晚发生时间 | \(vl[u]\) | 不推迟总工期的前提下最晚可以是几点 | \(vl[u] = \min_{(u\to v)}\{vl[v] - w\}\)，按拓扑逆序倒推 |
| 活动最早开始时间 | \(e(a) = ve[u]\) | 起点事件一发生就能开工 | |
| 活动最晚开始时间 | \(l(a) = vl[v] - w\) | 再晚就要拖累终点事件 |
总工期 \(T = \max_v ve[v]\)（若图有唯一汇点，就是汇点的 \(ve\)）。
活动的机动时间（slack / float）：
| slack | 含义 |
|---|---|
| \(> 0\) | 这个活动可以晚开工 slack 那么久，不影响总工期 |
| \(= 0\) | 关键活动——一分钟都不能拖，拖了整个工程就延期 |
关键路径 = 全部由关键活动构成的路径，长度恰好等于总工期 \(T\)。
三条必须记住的结论： 1. 关键路径可能不唯一（多条同样长的路径都是关键路径）； 2. 加快非关键活动毫无用处； 3. 加快关键活动也未必缩短工期——因为缩短之后关键路径可能换成另一条。 工程管理上这叫「瓶颈转移」。
模板¶
# [片段]
from collections import deque
def critical_path(n, edges):
"""AOE 网的关键路径。事件（顶点）编号 1..n，edges = [(u, v, w)] 是活动。
返回 (T, ve, vl, key)：
T —— 总工期
ve —— 事件最早发生时间（拓扑序正推）
vl —— 事件最晚发生时间（拓扑逆序倒推）
key —— 关键活动列表（机动时间为 0 的活动）
图有环时返回 None。复杂度 O(n + m)，**没有任何 log**。
"""
g = [[] for _ in range(n + 1)]
indeg = [0] * (n + 1) # 入度 = 该事件还有几个前驱活动没完成
for u, v, w in edges:
g[u].append((v, w))
indeg[v] += 1
# ---- 1. 拓扑排序 ----
d = indeg[:] # 拷一份来消耗，原始 indeg 留着不动
q = deque(i for i in range(1, n + 1) if d[i] == 0) # 入度 0 = 无前置条件，可以立刻开始
topo = []
while q:
u = q.popleft()
topo.append(u)
for v, w in g[u]:
d[v] -= 1
if d[v] == 0: # 最后一个前驱刚被去掉，v 现在可以入列
q.append(v)
if len(topo) != n:
return None # 有环 -> 不是合法的 AOE 网
# ---- 2. 正推 ve：最早发生时间（就是「DAG 上的最长路」）----
ve = [0] * (n + 1) # 源点没有前驱，最早发生时间就是 0
for u in topo: # 拓扑序保证：轮到 u 时它的前驱全部定稿
vu = ve[u]
for v, w in g[u]:
if vu + w > ve[v]: # 取 max：所有前驱活动都干完 v 才能发生
ve[v] = vu + w
T = max(ve[1:]) if n else 0 # 总工期取全体最大，多汇点也对
# ---- 3. 倒推 vl：最晚发生时间 ----
vl = [T] * (n + 1) # ★ 初值是总工期，不是 0
for u in reversed(topo): # 拓扑逆序保证「后继已算好」
best = vl[u] # 无出边的汇点保持 T，正是它的最晚发生时间
for v, w in g[u]:
if vl[v] - w < best: # 取 min：被最紧的那个后继卡住
best = vl[v] - w
vl[u] = best
# ---- 4. 挑出机动时间为 0 的活动 ----
key = [(u, v, w) for u, v, w in edges if ve[u] == vl[v] - w] # 最早 = 最晚，一刻都拖不得
return T, ve, vl, key
自测（数据结构教材里的经典 9 事件 13 活动 AOE 网）：
| 输入 | 输出 |
|---|---|
| 活动 \((1,2,3)(1,3,2)(2,4,2)(2,5,3)(3,4,4)(3,6,3)(4,5,2)(4,6,1)(5,7,2)(5,8,1)(6,8,3)(7,9,1)(8,9,2)\) | \(T = 12\)；关键活动 \((1,3,2)(3,4,4)(4,6,1)(6,8,3)(8,9,2)\) |
验算：\(2+4+1+3+2 = 12\) ✓，关键路径是 \(1\to3\to4\to6\to8\to9\)。
两个实现坑： 1.
vl的初值必须是 \(T\) 而不是 0 或INF。所有「没有出边的事件」 （汇点）的最晚发生时间就是 \(T\)，而vl的递推是取min， 初值给小了会把答案压死，给INF则汇点算不出来； 2. 多个源点 / 多个汇点是合法的。\(T\) 要取 \(\max_v ve[v]\) 而不是ve[n]—— 别假设 \(n\) 号点一定是唯一汇点。
117.4 DAG 上的最长路与最短路计数¶
关键路径的第 2 步（正推 \(ve\)）其实就是DAG 上的最长路。 把它单独拎出来讲，因为它解决了一个一般图上做不到的事。
| 图 | 最短路 | 最长路 |
|---|---|---|
| DAG | 拓扑序 DP，\(O(n+m)\) | ✅ 拓扑序 DP，\(O(n+m)\) |
| 非负权一般图 | Dijkstra，\(O(m\log m)\) | ❌ NP 困难（含哈密顿路径） |
| 含负权无负环 | Bellman-Ford / SPFA | ❌ NP 困难 |
「最长路」只在 DAG 上是多项式可解的。 所以看到「最长路」三个字，第一反应是确认图是不是 DAG； 不是 DAG 就先 Tarjan 缩点（112 章）—— 缩点之后一定是 DAG，这是缩点最常见的用途。
# [片段]
def dag_longest(n, topo, g, src=None):
"""DAG 上的最长路。topo 是拓扑序，g[u] = [(v, w), ...]。
src 为 None 时求「任意起点出发的最长路」（所有点初值 0）；
指定 src 时求「从 src 出发」（其余点初值 -inf）。
复杂度 O(n + m)。
"""
NEG = float('-inf')
dp = [0] * (n + 1) if src is None else [NEG] * (n + 1) # 初值决定「允许从哪里起步」
if src is not None:
dp[src] = 0
for u in topo: # 按拓扑序，轮到 u 时 dp[u] 已是最终值
du = dp[u]
if du == NEG:
continue # src 到不了 u，从 u 出发的转移全部无意义
for v, w in g[u]:
if du + w > dp[v]: # 最长路取 max，其余与最短路一模一样
dp[v] = du + w
return dp
DAG 上的最短路计数：比 SPFA 版简单得多¶
91 章 给了 S4 的 SPFA 计数模板，它需要两个数组
（F 是「还没传递出去的方案数」、S 是答案）和「在不在队列里」的判断，
原因是一个点可能被反复松弛，计数会重复累加。
在 DAG 上这个麻烦消失了：拓扑序保证每个点只被处理一次， 处理它时所有前驱都已经定稿。
# [片段]
def dag_count_shortest(n, topo, g, src, MOD=10 ** 9 + 7):
"""DAG 上的最短路长度与最短路条数，一遍拓扑序搞定。
★ 对比 91 章的 SPFA 版：这里**不需要** F/S 两个数组，
也不需要判断「在不在队列里」—— 拓扑序天然保证每个点只结算一次。
"""
INF = float('inf')
dist = [INF] * (n + 1)
ways = [0] * (n + 1)
dist[src] = 0
ways[src] = 1 # 「原地不动」本身算一条路径，递推的起点
for u in topo:
if dist[u] == INF:
continue # src 到不了 u，别拿 INF 去参与加法
du, wu = dist[u], ways[u] # 缓存成局部变量，内层循环里要反复读
for v, w in g[u]:
nd = du + w
if nd < dist[v]:
dist[v] = nd
ways[v] = wu # 找到更短的路 -> 计数重来
elif nd == dist[v]:
ways[v] = (ways[v] + wu) % MOD # 同长 -> 累加
return dist, ways
一般图上的最短路计数怎么办？两条路：
| 图 | 做法 |
|---|---|
| DAG | 上面这段，\(O(n+m)\) |
| 非负权一般图 | Dijkstra 的出队顺序就是一个拓扑序！按出队顺序做上面的累加即可 |
| 含 0 权环 | ⚠️ 方案数无穷，题目必须排除这种情况 |
| 含负权 | SPFA 两数组版（91 章） |
「Dijkstra 的出队顺序是最短路 DAG 的拓扑序」是一个非常有用的观察： 边权全正时，最短路径构成的子图一定是 DAG， 而 Dijkstra 恰好按 \(dist\) 升序确定每个点——那正是这个 DAG 的一个拓扑序。 于是「最短路计数」「最短路上的 DP」「求次短路」全都可以在 Dijkstra 出队时顺手做掉。
117.5 最小环：无向图与有向图的分野¶
S4 的清单里「Floyd 判最小环」和 k 短路排在一起。 91 章 已经给了完整的 Python 实现， 这里只补一件 91 章没说的事：无向图和有向图的最小环，做法不一样。
| 图 | 做法 | 复杂度 | 要点 |
|---|---|---|---|
| 无向图 | Floyd 变形：枚举环上编号最大的点 \(k\) 和它的两个邻居 \(i,j\) | \(O(n^3)\) | 必须在做第 \(k\) 轮松弛之前统计，且 \(i\to j\) 用最短路矩阵、\(i\to k\) / \(k\to j\) 用原始边权 |
| 有向图 | ① Floyd 后取 \(\min_i W[i][i]\)；② 或对每个点跑 Dijkstra | \(O(n^3)\) / \(O(nm\log m)\) | 有向图不存在「一条边被算两次」的问题，简单得多 |
| 有向图、\(n\) 大而 \(m\) 小 | 枚举每条边 \((u,v,w)\)，删掉它后求 \(v\to u\) 的最短路 | \(O(m\cdot m\log m)\) | 稀疏图上更快 |
为什么无向图麻烦：无向图里 \(W[i][j]\) 可能就是「\(i\to k \to j\)」这条路， 于是「\(i\to j\) 最短路 + 边 \(ik\) + 边 \(kj\)」会把边 \(ik\) 走两遍， 得到一个长度为 \(2w_{ik}\) 的假环。所以必须： - 用做第 \(k\) 轮之前的 \(g[i][j]\)（此时它只允许经过编号 \(< k\) 的点，不可能经过 \(k\)）； - \(i\to k\)、\(k\to j\) 两段用原始边权矩阵 \(w\)，不是最短路矩阵 \(g\)。
这两点缺一个就会算出假环，是 91 章那段代码里
w和g必须是两个矩阵的原因。
117.6 Python 下的可行规模¶
A* 求 k 短路¶
瓶颈是堆的大小，不是循环次数。
| \(n\) | \(m\) | \(k\) | \(nk\) | 堆峰值元素数 | 估时 | 判断 |
|---|---|---|---|---|---|---|
| \(10^3\) | \(10^4\) | \(10^2\) | \(10^5\) | \(\approx10^5\) | 0.3 s | ✅ |
| \(5\times10^3\) | \(10^5\) | \(10^3\) | \(5\times10^6\) | ⚠️ 约 500 MB | 10–20 s | ⚠️ 内存先炸 |
| \(10^3\) | \(10^5\) | \(10^3\) | \(10^6\) | \(\approx10^6\)（约 100 MB） | 3–6 s | ⚠️ |
| \(10^4\) | \(10^5\) | \(10^4\) | \(10^8\) | ❌ | ❌ | ❌ |
两条省内存的手段： 1.
if h[v] == INF: continue——到不了终点的点根本不入队， 在有大量死路的图上能省掉一大半； 2. 元组换成整数编码：f * (n+1) * BIG + ...把(f, g, u)压成一个int， 堆里存int而不是tuple，内存少 3–4 倍、比较也更快。 前提是 \(f, g\) 有明确上界。
关键路径 / DAG DP¶
| 项 | 复杂度 | \(n=m=10^6\) 的估时 |
|---|---|---|
拓扑排序（deque） |
\(O(n+m)\) | 1.5–2 s |
| 正推 \(ve\) | \(O(n+m)\) | 1–1.5 s |
| 倒推 \(vl\) | \(O(n+m)\) | 1–1.5 s |
| 挑关键活动 | \(O(m)\) | 0.5 s |
关键路径是本章唯一「Python 完全没有劣势」的算法： 全程线性、没有 \(\log\)、没有堆、没有递归。 \(n = m = 10^6\) 在 5 秒内可以做完（瓶颈其实是读入 \(3\times10^6\) 个 token）。 别被「关键路径」这个名字吓到——它比 Dijkstra 简单也快。
汇总¶
| 算法 | 复杂度 | Python 可行规模 |
|---|---|---|
| 关键路径 / DAG 最长路 / DAG 计数 | \(O(n+m)\) | \(10^6\) ✅ |
| 反图 Dijkstra（估价函数预处理） | \(O(m\log m)\) | \(2\times10^5\) ✅ |
| A* 求 k 短路 | \(O(m\log m + nk\log(nk))\) | \(nk \le 10^6\) ⚠️ |
| Floyd 判最小环（无向） | \(O(n^3)\) | \(n \le 200\)（用 map 优化，见 91 章） |
| 有向图最小环（\(n\) 次 Dijkstra） | \(O(nm\log m)\) | \(n \le 10^3, m \le 10^4\) ⚠️ |
| Yen 算法（简单路径 k 短路） | \(O(kn(m+n\log n))\) | ❌ |
| 可持久化可并堆求 k 短路 | \(O(m\log m + k\log k)\) | ❌ 常数太大 |
117.7 例题¶
BISHI109 邮递员送信（中等）¶
\(n \le 10^3\) 个路口、\(m \le 10^5\) 条单向道路，\(w \le 10^4\)。 1 号点是邮局，\(2\sim n\) 各有一件包裹；每送一件必须返回邮局才能取下一件。 求送完全部 \(n-1\) 件并回到邮局的最短总时间。保证任意两点互相可达。 时限：C/C++ 1 秒，其他语言 2 秒。 题面见 BISHI109 原题（牛客）。
✅ 题解见
solutions/BISHI109.py，已通过官方样例验证。 本题在 91-最短路 是主讲（建图技巧视角）； 这里作为「反图最短路 = k 短路的估价函数」的前置演练。
这题为什么放在本章：它是反图技巧的最小完整案例，
而反图最短路正是 117.2 里 A* 估价函数的全部内容。把这题写熟，
kth_shortest 里那两行 build_csr(n, vs, us, ws) + dijkstra(..., t) 就不用再想了。
| 部分 | 朴素做法 | 正确做法 |
|---|---|---|
| 去程 \(\text{dist}(1\to v)\) | 原图上从 1 跑一次 Dijkstra | 同 |
| 回程 \(\text{dist}(v\to 1)\) | 逐点跑 → \(n\) 次 Dijkstra，\(n=10^3\) 时 \(10^8\) 级别 ❌ | 反图上从 1 跑一次 Dijkstra ✅ |
一句话：在反图上从 \(s\) 出发的单源最短路， 就是原图上「所有点到 \(s\)」的最短路。\(n\) 次变 1 次。 这一招在 k 短路（\(h[u] = \text{dist}(u\to t)\)）、 「所有点到最近的关键点」、次短路里都是同一个套路。
import sys
from heapq import heappush, heappop
def build_csr(n, us, vs, ws):
"""把边表压成 CSR：返回 (start, to, wt)。"""
m = len(us)
deg = [0] * (n + 2) # 先统计出度，才能算出每个点占哪一段
for u in us:
deg[u] += 1
start = [0] * (n + 2)
acc = 0
for i in range(1, n + 1):
start[i] = acc # 出度前缀和（不含自己）= 该点的起始下标
acc += deg[i]
start[n + 1] = acc # 哨兵，让 start[u+1] 对 u = n 也有定义
pos = start[:] # pos[u] = u 的下一个空槽，边填边右移
to = [0] * acc
wt = [0] * acc
for i in range(m):
u = us[i]
k = pos[u]
to[k] = vs[i]; wt[k] = ws[i] # 终点与边权共用下标，遍历时一次取两个
pos[u] = k + 1
return start, to, wt
def dijkstra(n, start, to, wt, src):
INF = float('inf')
dist = [INF] * (n + 1) # INF 同时表示「未到达」
dist[src] = 0
heap = [(0, src)] # (距离, 点)，元组按第一项排序正是需要的
while heap:
d, u = heappop(heap)
if d > dist[u]: # 懒删除：heapq 没有 decrease-key
continue # d 比现有的还差，说明这是过期副本
for i in range(start[u], start[u + 1]): # CSR 里 u 的出边就是这段下标
v = to[i]
nd = d + wt[i]
if nd < dist[v]: # 松弛成功才入堆，堆里因此会有同点的多份记录
dist[v] = nd
heappush(heap, (nd, v))
return dist
def main() -> None:
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
us = [0] * m; vs = [0] * m; ws = [0] * m # 三个平行数组存边，比 m 个元组省内存
p = 2 # 前两个 token 是 n 和 m
for i in range(m):
us[i] = int(data[p]); vs[i] = int(data[p + 1]); ws[i] = int(data[p + 2])
p += 3 # 每条边三个数
d1 = dijkstra(n, *build_csr(n, us, vs, ws), src=1) # 去程：1 -> v
d2 = dijkstra(n, *build_csr(n, vs, us, ws), src=1) # ★ 反图上 1 -> v 即 v -> 1
total = 0
for v in range(2, n + 1): # 从 2 起：1 号点是邮局，不用送
total += d1[v] + d2[v] # 每件包裹的往返代价
sys.stdout.write("%d\n" % total)
main()
四个坑（来自题解记录）：
- 道路是单向的，反图必须真的把
us、vs换位重新建表，不能直接复用原图； - Dijkstra 用
heapq的标准懒删除写法（弹出时if d > dist[u]: continue）——heapq没有decrease-key，这是唯一正确姿势； - 可能有重边（样例里 \(3\to5\) 出现两次，权都是 6），Dijkstra 天然处理；
- 答案可达 \(10^3 \times 2 \times (10^3\times10^4) = 2\times10^{10}\) 级别，
C++ 要
long long；Python 无忧。
顺带一句关于 \(n\) 只有 1000：朴素 \(O(n^2)\) 的 Dijkstra 也是 \(10^6\) 能过。 但 \(m\) 到 \(10^5\) 时堆优化更稳，而且是通用写法——优先写通用写法。
BISHI108 最优乘车（简单）¶
\(M \le 100\) 条单向巴士线路、\(N \le 500\) 个站，每条线路按次序经过 \(s\) 个站。 求从 1 号站到 \(N\) 号站的最少换乘次数；到不了输出
NO，无需换乘输出 0。 时限：C/C++ 1 秒，其他语言 2 秒。 题面见 BISHI108 原题（牛客）。✅ 题解见
solutions/BISHI108.py，已通过官方样例验证。 本题在 91-最短路 是主讲； 这里从「虚拟链 = AOE 链」的视角看它与关键路径的同源性。
核心转化：\(\text{最少换乘次数} = \text{最少乘车段数} - 1\)。
朴素建图会爆：同一条线路上「前面的站 → 后面的站」各连一条权 1 的边， 一条 \(s\) 站的线路要连 \(s^2/2\) 条边，\(100 \times 500\) 站 → \(1.25\times10^7\) 条， Python 建图就先跪了。
正解：拆点 + 虚拟链。对每条线路的每个位置 \(i\) 建一个「车上」节点 \(R_i\)：
站台 t_i --权 1--> R_i （上车，多坐一趟车）
R_i --权 0--> R_{i+1} （继续往前开，免费；★ 天然保证只能顺向）
R_i --权 0--> 站台 t_i （下车，免费）
| 建法 | 边数 | \(M=100, s=500\) |
|---|---|---|
| 站 → 站全连 | \(O(s^2)\) | \(1.25\times10^7\) ❌ |
| 虚拟链 | \(O(s)\) | \(1.5\times10^5\) ✅ |
「虚拟链」和 AOE 网是同一个构造： \(R_1 \to R_2 \to \cdots \to R_s\) 是一条零权链， 它表达的正是「工序必须按顺序进行」——这就是 AOE 网里「顶点是事件、边是活动」的思路。 看到「一条序列上任意两点之间要连边」，就该想到「串成一条链，把 \(O(s^2)\) 降到 \(O(s)\)」， 这在前缀和优化建图、线段树优化建图里是同一个母题。
边权只有 0 和 1 → 0-1 BFS（双端队列），连堆都省了，复杂度 \(O(V+E)\)：
import sys
from collections import deque
def main() -> None:
data = sys.stdin.buffer.read().split()
M = int(data[0]); N = int(data[1]) # ★ M 在前、N 在后，顺序容易读反
lines = []
p = 2 # 前两个 token 是 M 和 N
total_stops = 0 # 所有线路的站次总数，决定要开多少虚拟点
for _ in range(M):
s = int(data[p]); p += 1 # 本条线路的站数
stops = [int(v) for v in data[p:p + s]]; p += s # 紧跟着的 s 个 token 是站号
lines.append(stops)
total_stops += s
# 节点编号：1..N 是站台，N+1.. 是各线路各位置的「车上」节点
V = N + total_stops + 1 # 加 1 是因为站台从 1 开始编，下标 0 空着
adj = [[] for _ in range(V)]
nid = N + 1 # 下一个可用的虚拟点编号
for stops in lines:
base = nid # 本条线路的虚拟点占 [base, base+s)
s = len(stops)
for i, st in enumerate(stops):
r = base + i # 「在这条线路的第 i 站上车」这个状态
adj[st].append((r, 1)) # 上车：算一趟车
adj[r].append((st, 0)) # 下车：免费
if i + 1 < s:
adj[r].append((r + 1, 0)) # 继续往前开：免费，且只能顺向
nid += s # 让下一条线路接着往后编号，互不重叠
INF = float('inf')
dist = [INF] * V
dist[1] = 0 # 从 1 号站台出发，还没上过车
dq = deque([(0, 1)]) # 0-1 BFS 必须用双端队列
while dq:
d, u = dq.popleft()
if d > dist[u]: # 懒删除，过期记录跳过
continue
for v, w in adj[u]:
nd = d + w
if nd < dist[v]:
dist[v] = nd
if w:
dq.append((nd, v)) # 权 1 放队尾
else:
dq.appendleft((nd, v)) # 权 0 放队首
# 两端各自有序，队列整体仍是距离非降，故无需堆
d = dist[N]
sys.stdout.write("NO\n" if d == INF else "%d\n" % (d - 1)) # 段数减 1 才是换乘次数
main()
样例复核：\(1 \to\) 上第 3 条线（2 1 3 5）在位置 2 \(\to\) 坐到 3（1 段）
\(\to\) 上第 2 条线（4 7 3 6）在位置 3 \(\to\) 坐到 6（2 段）
\(\to\) 上第 1 条线（6 7）在位置 1 \(\to\) 坐到 7（3 段）。换乘 \(3-1 = 2\) ✓
四个坑：
- 输入第一行是 \(M\)（线路数）在前、\(N\)（站数）在后，顺序极易读反；
- 答案是「乘车段数 \(-1\)」，无需换乘时输出 0；
- 到不了要输出
NO（大写）； - 0-1 BFS 的队列必须是
collections.deque（要用appendleft），list根本没有 \(O(1)\) 的头插；出队时同样要if d > dist[u]: continue。
0-1 BFS 与 A* 的关系：两者都是「让优先队列变便宜」。 0-1 BFS 发现「只有两种优先级」，于是用双端队列代替堆，去掉 \(\log\)； A* 发现「有额外信息 \(h\)」，于是让堆更早地弹出正确答案。 看到边权只有 0/1 就用 deque，看到有精确的 \(h\) 就用 A*——这两句是本章的实用结论。
想练手 k 短路与关键路径的话¶
| 想练 | 推荐题 |
|---|---|
| A* 求 k 短路 | 洛谷 P2483【模板】k 短路 / [SDOI2010] 魔法猪学院、POJ 2449 Remmarguts' Date |
| A* 的一般形式 | 洛谷 P1379 八数码难题（\(h\) = 曼哈顿距离和） |
| 关键路径 | 洛谷 P1113 杂务（AOV 版最早完成时间）、洛谷 P1685 游览 |
| DAG 最长路 | 洛谷 P1137 旅行计划、洛谷 P4017 最大食物链计数 |
| 最短路计数 | 洛谷 P1144 最短路计数（无权图，BFS 版） |
| Floyd 判最小环 | 洛谷 P6175 无向图的最小环问题 |
117.8 本章速查¶
| 要点 | 结论 |
|---|---|
| A* 的排序键 | \(f = g + h\)（已走 + 估计还要走） |
| \(h\) 必须可采纳 | \(h \le\) 真实剩余距离，否则解不最优 |
| \(h = 0\) 时 | A* \(\equiv\) Dijkstra |
| k 短路的完美 \(h\) | \(h[u] = \text{dist}(u \to t)\)，在反图上一次 Dijkstra 求得 |
| k 短路的正确性 | \(h\) 精确 → \(f\) 就是完整路径长 → 第 \(i\) 次弹出 \(t\) 即第 \(i\) 短 |
| k 短路的剪枝 | cnt[u] > k 就丢弃（每个点最多有效扩展 \(k\) 次） |
| k 短路的另一个剪枝 | h[v] == INF 的点根本不入队 |
| k 短路的定义陷阱 | 「可重复经过点」→ A*；「简单路径」→ Yen，Python 没戏 |
| k 短路的瓶颈 | 堆的大小 \(O(m + nk)\)（内存，不是时间） |
| AOV 网 | 顶点 = 活动 → 拓扑排序 |
| AOE 网 | 顶点 = 事件，边 = 活动 → 关键路径；必须是 DAG |
| \(ve[v]\) | 事件最早发生：\(\max(ve[u]+w)\)，拓扑序正推 |
| \(vl[u]\) | 事件最晚发生：\(\min(vl[v]-w)\)，拓扑逆序倒推 |
vl 的初值 |
\(T\)（总工期），不是 0 也不是 INF |
| 总工期 \(T\) | \(\max_v ve[v]\)，别假设 \(n\) 号点是唯一汇点 |
| 活动的机动时间 | \(vl[v] - w - ve[u]\) |
| 关键活动 | 机动时间 \(= 0\) |
| 关键路径 | 全由关键活动构成，长度 \(= T\) |
| 三条工程结论 | 关键路径可能不唯一；加快非关键活动无用；加快关键活动也可能瓶颈转移 |
| 最长路 | 只在 DAG 上多项式可解；一般图是 NP 困难 |
| 不是 DAG 怎么办 | Tarjan 缩点（112 章），缩完一定是 DAG |
| DAG 最短路计数 | 一遍拓扑序，不需要 SPFA 版的两个数组 |
| Dijkstra 的出队顺序 | 就是最短路 DAG 的一个拓扑序 → 计数/DP/次短路都能顺手做 |
| 0 权环 + 计数 | ⚠️ 方案数无穷，题目必须排除 |
| 无向图最小环 | Floyd 变形：先统计再松弛，\(i\to j\) 用 \(g\)、两条边用 \(w\) |
| 无向图为什么麻烦 | 不然会把同一条边走两遍，得到假环 |
| 有向图最小环 | Floyd 后取 \(\min W[i][i]\)，简单得多 |
| 虚拟链 | 「序列上任意两点连边」\(O(s^2)\) → 串成链 \(O(s)\) |
| 0-1 BFS | 边权只有 0/1 → deque，权 0 appendleft、权 1 append |
| 反图 | 在反图上从 \(s\) 跑一次 = 原图「所有点到 \(s\)」，\(n\) 次变 1 次 |
| 数据规模 → Python 现实性（本章算法） |
|---|
| 关键路径 / DAG 最长路 / DAG 计数，\(n=m\le10^6\) |
| 反图 Dijkstra，\(m \le 2\times10^5\) |
| A* 求 k 短路，\(nk \le 10^5\) |
| A* 求 k 短路，\(nk \approx 10^6\) |
| A* 求 k 短路，\(nk \ge 10^7\) |
| Floyd 判最小环（无向），\(n \le 200\) |
| 有向图最小环（\(n\) 次 Dijkstra），\(n\le10^3, m\le10^4\) |
| Yen 算法（简单路径 k 短路） |
| 可持久化可并堆求 k 短路 |