PYTHON LESSON 122
最短路进阶：路径条数与路线还原
在 Dijkstra 模板上学会统计最短路条数与还原具体路线，拿下“最短距离 + 方案数”复合题型。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- nd < dist[v] 更短：dist、cnt、pre 一起更新
- nd == dist[v] 一样短：cnt[v] += cnt[u]
- 从终点沿 pre 回溯再 reverse 得到完整路线
01 · 核心概念
Dijkstra 的两大扩展：cnt 数组数方案、pre 数组还原路线
Dijkstra 的两大扩展：cnt 数组数方案、pre 数组还原路线：GESP 真题很爱把两个问题绑在一起：最短距离是多少？这样的路线有几条？好消息是骨架不用换——Dijkstra 照跑，只要多带一个 cnt 数组和一个 pre 字典，两个扩展一次学会。
GESP Python 8 级 · 单源最短路（Dijkstra）GESP Python 8 级 · 计数原理有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
02 · 语法与规则
先记住这 3 条，再开始写程序
nd < dist[v] 更短：dist、cnt、pre 一起更新先准确读出这条写法的结构与作用。
nd == dist[v] 一样短：cnt[v] += cnt[u]换一组最小数据，手工推演一次结果。
从终点沿 pre 回溯再 reverse 得到完整路线再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# Dijkstra 两大扩展：数一数最短路有几条，再把路线打印出来
import heapq
graph = { # 邻接表：{路口: [(下一路口, 距离), ...]}
1: [(2, 2), (3, 3)],
2: [(3, 1), (4, 4)],
3: [(4, 2)],
4: [],
}
start, end = 1, 4
dist = {start: 0}
cnt = {start: 1} # cnt[v] = 到 v 的最短路有多少条
pre = {} # pre[v] = 最短路上 v 的前一个路口
heap = [(0, start)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # 过期记录，跳过
for v, w in graph[u]:
nd = d + w
if v not in dist or nd < dist[v]: # 找到更短的路
dist[v] = nd
cnt[v] = cnt[u] # 方案数直接继承
pre[v] = u
heapq.heappush(heap, (nd, v))
elif nd == dist[v]: # 一样短，方案数累加
cnt[v] += cnt[u]
print("1 到 4 的最短距离:", dist[end])
print("最短路线共有:", cnt[end], "条")
path = [end]
while path[-1] != start: # 从终点沿 pre 一路回溯
path.append(pre[path[-1]])
path.reverse()
print("其中一条路线:", " -> ".join(map(str, path)))1 到 4 的最短距离: 5 最短路线共有: 2 条 其中一条路线: 1 -> 3 -> 4
两条并列最短路线是 1→2→3→4 与 1→3→4，长度都是 5；程序沿 pre 回溯只打印其中一条，另一条请你在图上找出来。
04 · 逐步理解
每一步只解决一个问题
- 01
从“最短”到“有几条”
GESP 真题很爱把两个问题绑在一起：最短距离是多少？这样的路线有几条？好消息是骨架不用换——Dijkstra 照跑，只要多带一个 cnt 数组和一个 pre 字典，两个扩展一次学会。
- 02
cnt 数组的两条更新规则
规则一：找到更短的路（nd < dist[v]），v 的方案数直接“继承”u 的方案数——因为所有更短路线都是先到 u 再走这条边。规则二：一样短（nd == dist[v]），把 u 的方案数累加进 cnt[v]。就这两条，背下来。
if nd < dist[v]: cnt[v] = cnt[u] elif nd == dist[v]: cnt[v] += cnt[u] - 03
为什么更短时要“重置”而不是累加
dist[v] 被刷新，说明之前记录的那些路线全部不再是“最短”的了，方案数必须推倒重来、从新前驱继承。如果这时还累加，就会把已经落伍的长路线也数进去——这是本题型最容易踩的坑。
cnt[v] = cnt[u] # 更短：推翻旧方案，整体继承 - 04
pre 字典与路线回溯
每次更新最短路时顺手记下 pre[v] = u，相当于给每个路口留了一张“你从哪来”的纸条。查询时从终点出发一路读纸条回到起点，再 reverse 一下，正向路线就出来了。
path = [end] while path[-1] != start: path.append(pre[path[-1]]) path.reverse() - 05
条数太大要取模
在网格状的图上，最短路条数可以是组合数级别（想想 123 课的网格路径），题目会要求对 10^9+7 取模。改动只有一处：累加时顺手 % MOD。注意继承不用取模，因为 cnt[u] 本来就已经取过了。
cnt[v] = (cnt[v] + cnt[u]) % MOD - 06
复杂度没有变
两个扩展都只是数组的 O(1) 读写，整体仍是 O(m log n)。配套真题 py-exam-l8-a2 给到 10^5 个点、2×10^5 条边，邻接表加堆优化的这套写法稳过——模板熟了，考场上就是默写。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行分析器，核对最短距离 5、共 2 条
- 2在图上找出两条并列的最短路线
- 3解释为什么找到更短路时 cnt 要重置而不是累加
- 4把 1→3 的距离改成 5，预测并核对条数变化
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
核心数据结构树、图、DFS、BFS 与最短路从节点与边的模型出发，掌握遍历、连通性、树结构、最小生成树和最短路径的适用条件。＋
正式定义
图由顶点和边构成；树是连通且无环的无向图。DFS 沿路径深入后回溯，BFS 按距离层次扩展。算法的正确选择取决于图是否有向、边权是否为负、是否稠密以及目标是遍历、连通还是最短路。
必须掌握
- 邻接矩阵占 O(V²) 空间，适合稠密图和快速查边；邻接表占 O(V+E)，适合稀疏图。
- DFS 常用递归或显式栈，BFS 使用队列；一般图都必须记录 visited 防止重复和死循环。
- 无权图的 BFS 首次到达即得到最少边数距离，可用 parent 还原路径。
- 树有 V-1 条边且任意两点路径唯一；二叉树前/中/后序描述根的访问时机。
- Dijkstra 只适用于非负边权；Floyd 求所有点对最短路并允许负边，但不能有可达负环。
- Kruskal 按边权排序并用并查集避环，得到连通无向带权图的最小生成树。
常见误区
- 遍历一般图时不记录 visited
- 对负权边使用 Dijkstra
- 混淆最短路径树与最小生成树
- 递归 DFS 忽略深度限制
适用边界
- 有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
- 网格搜索也是图搜索：格子是顶点，可移动关系是边；不要只背二维数组模板。
算法方法算法、复杂度与解题验证把题意转成输入、状态、规则与输出，用正确性和复杂度共同评价解法。＋
正式定义
算法是解决一类问题的有限、明确步骤。正确性说明算法对所有满足前置条件的输入都得到规定结果；时间和空间复杂度描述输入规模增长时资源使用的增长量级。
必须掌握
- 先明确输入规模 n、数据范围、目标和允许误差，再选择数据结构与算法。
- O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 表示增长量级，不是精确运行秒数。
- 顺序代码复杂度取较大项，嵌套循环常相乘，二分每步把范围缩小一半。
- 正确性可用循环不变量、数学归纳、交换论证、反证或状态定义来说明。
- 样例只验证少量输入；必须自己设计边界、极端、重复、有序/逆序和无解数据。
- 优化前先得到正确基线并测量瓶颈，不为小数据盲目增加复杂实现。
常见误区
- 只看样例通过就宣称正确
- 不看数据范围使用 O(n²)
- 二分区间开闭混用
- 把 O(n) 当成永远比 O(log n) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
算法方法质数、约数、最大公因数与筛法建立整数整除体系，掌握试除、欧几里得算法、唯一分解和筛法的条件与复杂度。＋
正式定义
若整数 a 能被非零整数 b 整除，则 b 是 a 的约数。大于 1 且只有 1 和自身两个正约数的整数是质数；每个大于 1 的整数都能唯一分解为质数幂的乘积（忽略次序）。
必须掌握
- 0 和 1 都不是质数；判定 n 是否为质数只需试除到 floor(sqrt(n))。
- gcd(a,b)=gcd(b,a mod b) 构成欧几里得算法；lcm(a,b)=abs(a//gcd(a,b)*b) 并要处理 0。
- 约数成对出现，可枚举到平方根；完全平方数的平方根只计一次。
- 埃氏筛从 p² 开始标记质数 p 的倍数，总体 O(n log log n)；线性筛保证每个合数被最小质因子筛一次。
- 分解质因数后，约数个数与约数和可以由各质因数指数公式计算。
- 模运算支持加减乘分配；模除法不能直接用整数除法，需满足可逆条件并求逆元。
常见误区
- 把 1 判成质数
- 试除上界漏掉平方根
- 完全平方数的约数重复统计
- 取模后直接做普通除法
适用边界
- 大整数质性测试和密码学分解需要更高级算法，不应把试除法扩展到任意规模。
- 题目若涉及负数约数、0 的约数或模数非质数，必须先明确数学定义。
数学基础计数原理、组合数与计算几何基础明确有序/无序、互斥/分步与几何退化边界，再把公式转为稳定程序。＋
正式定义
加法原理用于互斥方案分类求和，乘法原理用于依次完成步骤求积；排列关心顺序，组合不关心顺序。计算几何用坐标、向量、距离和方向关系把图形条件转成数值判定。
必须掌握
- A(n,m)=n!/(n-m)!，C(n,m)=n!/(m!(n-m)!)，并有 C(n,m)=C(n,n-m)。
- 杨辉三角递推 C(n,m)=C(n-1,m-1)+C(n-1,m)，边界 C(n,0)=C(n,n)=1。
- 取模下的组合数算法取决于 n、模数是否为质数、查询次数和是否允许预处理。
- 距离比较应优先比较平方，避免不必要的 sqrt 和浮点误差。
- 三角形必须满足任意两边之和大于第三边；共线、重合、零长度是几何边界。
- 浮点比较应按题目误差使用容差；整数坐标能用叉积时优先保持整数计算。
常见误区
- 未判断顺序是否重要就套排列组合公式
- 模意义下直接做普通除法
- 浮点数直接用 ==
- 漏掉共线或退化图形
适用边界
- 概率需要在计数结果上再建立样本空间，不等同于组合数本身。
- 复杂计算几何涉及方向、相交、凸包等更多主题，本章只覆盖课程实际使用的基础判定。
完成检查