PYTHON LESSON 118
单源最短路：快递员的最优路线
理解 Dijkstra 的“最近点先确定”思想，会用 heapq 实现堆优化版单源最短路。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- import heapq 使用小顶堆
- heapq.heappush / heappop 存取 (距离, 点)
- if d > dist[u]: continue 跳过过期记录
01 · 核心概念
Dijkstra 算法与堆优化
Dijkstra 算法与堆优化：Dijkstra 每轮从堆中取出当前距离最小的点 u——它的最短路已经板上钉钉（非负边权保证不会再有更近的绕行）。然后用 u 去“松弛”它的邻居：经过 u 到 v 更近就更新 dist[v]。
GESP Python 8 级 · 单源最短路（Dijkstra）GESP Python 8 级 · 堆的应用有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
02 · 语法与规则
先记住这 3 条，再开始写程序
import heapq 使用小顶堆先准确读出这条写法的结构与作用。
heapq.heappush / heappop 存取 (距离, 点)换一组最小数据，手工推演一次结果。
if d > dist[u]: continue 跳过过期记录再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 送快递：Dijkstra 单源最短路（堆优化版）
import heapq
graph = { # 邻接表：{路口: [(下一路口, 距离), ...]}
1: [(2, 4), (3, 1)],
2: [(4, 3)],
3: [(2, 1), (4, 5)],
4: [],
}
start = 1 # 快递仓库在 1 号路口
dist = {start: 0}
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 # 找到更短的路，更新
heapq.heappush(heap, (nd, v))
for node in sorted(dist):
print("仓库 1 到路口", node, "的最短距离:", dist[node])仓库 1 到路口 1 的最短距离: 0 仓库 1 到路口 2 的最短距离: 2 仓库 1 到路口 3 的最短距离: 1 仓库 1 到路口 4 的最短距离: 5
1→2 最短不是直达的 4，而是 1→3→2 共 2：绕路反而更近，这正是最短路要解决的问题。
04 · 逐步理解
每一步只解决一个问题
- 01
问题建模：路口与道路
把地图抽象成图：路口是点，道路是带长度的边。求从仓库（源点）到每个路口的最短距离，就是“单源最短路”问题。用邻接表存图：graph[u] 是 u 的所有出边 (v, w)。
graph = {1: [(2, 4), (3, 1)]} - 02
核心思想：最近的先“拍板”
Dijkstra 每轮从堆中取出当前距离最小的点 u——它的最短路已经板上钉钉（非负边权保证不会再有更近的绕行）。然后用 u 去“松弛”它的邻居：经过 u 到 v 更近就更新 dist[v]。
d, u = heapq.heappop(heap) - 03
堆优化：从 O(n²) 到 O(m log n)
朴素版每轮扫所有点找最小值，O(n²)；用 heapq 小顶堆，取最小值只要 O(log n)。n ≤ 10^4、m ≤ 10^5 的数据下，堆优化版轻松跑进 1 秒，朴素版可能超时。
import heapq heap = [(0, start)] - 04
过期记录：懒删除技巧
同一个点可能被多次压入堆（每次找到更短的路就压一次）。弹出时若 d > dist[u]，说明这条记录已被更优答案取代，直接 continue 跳过——不用费劲从堆里删它。
if d > dist[u]: continue - 05
松弛操作：最短路的肌肉记忆
“松弛”就是比较：d + w 与 dist[v] 谁小。dist[v] = min(dist[v], d + w) 是所有最短路算法的共同动作。不可达的点 dist 里不存在，最后输出时记为 −1 或“不可达”。
nd = d + w if v not in dist or nd < dist[v]: dist[v] = nd heapq.heappush(heap, (nd, v)) - 06
为什么不能有负权边
Dijkstra 的拍板逻辑依赖“距离只会越绕越长”。若有负权边，先确定的点可能被后来的负边“抄底”，结论就错了。含负边的题请换 Bellman-Ford；GESP 范围内记住这条限制即可。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行规划器，核对四个路口的最短距离
- 2手画邻接表，追踪堆里的每次弹出
- 3把 3→4 的距离改成 1 再跑一遍
- 4解释为什么 Dijkstra 不能处理负权边
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
核心数据结构树、图、DFS、BFS 与最短路从节点与边的模型出发，掌握遍历、连通性、树结构、最小生成树和最短路径的适用条件。＋
正式定义
图由顶点和边构成；树是连通且无环的无向图。DFS 沿路径深入后回溯，BFS 按距离层次扩展。算法的正确选择取决于图是否有向、边权是否为负、是否稠密以及目标是遍历、连通还是最短路。
必须掌握
- 邻接矩阵占 O(V²) 空间，适合稠密图和快速查边；邻接表占 O(V+E)，适合稀疏图。
- DFS 常用递归或显式栈，BFS 使用队列；一般图都必须记录 visited 防止重复和死循环。
- 无权图的 BFS 首次到达即得到最少边数距离，可用 parent 还原路径。
- 树有 V-1 条边且任意两点路径唯一；二叉树前/中/后序描述根的访问时机。
- Dijkstra 只适用于非负边权；Floyd 求所有点对最短路并允许负边，但不能有可达负环。
- Kruskal 按边权排序并用并查集避环，得到连通无向带权图的最小生成树。
常见误区
- 遍历一般图时不记录 visited
- 对负权边使用 Dijkstra
- 混淆最短路径树与最小生成树
- 递归 DFS 忽略深度限制
适用边界
- 有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
- 网格搜索也是图搜索：格子是顶点，可移动关系是边；不要只背二维数组模板。
Python 基础条件、循环与程序流程准确理解 if、for、while、range、break、continue 和循环嵌套，而不是背代码模板。＋
正式定义
控制流决定下一条要执行的语句。分支依据布尔条件选择路径；循环在满足规则时重复执行代码块。Python 用冒号和缩进界定代码块。
必须掌握
- if/elif/else 从上到下判断，只执行第一个为真的分支；else 不写条件。
- for 依次取得可迭代对象中的元素；range(start, stop, step) 包含 start、不包含 stop，step 不能为 0。
- while 在每轮开始前检查条件；循环体必须让状态向终止条件推进。
- break 结束最内层循环，continue 跳过本轮剩余语句，循环的 else 仅在没有被 break 终止时执行。
- 嵌套循环的总执行次数通常需要把各层次数相乘；内层 break 不会结束外层循环。
- 边界测试至少覆盖空范围、单个元素、第一项命中、最后一项命中和始终不命中。
常见误区
- range 的右端点多算或少算一次
- while 忘记更新状态造成死循环
- 把两个互斥条件写成两个独立 if
- 误以为 break 会跳出所有嵌套循环
适用边界
- 流程图是算法的表示方法，不是 Python 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
Python 基础运算符、表达式与优先级完整区分算术、比较、逻辑、成员、身份和位运算，并用优先级表消除歧义。＋
正式定义
表达式求值得到一个值。运算符规定如何组合操作数；当一个表达式含多个运算符时，优先级和结合方向决定求值顺序，括号可以明确改变顺序。
必须掌握
- / 总是得到浮点结果；// 是向负无穷方向取整的整除；% 与 // 满足 a == (a // b) * b + a % b。
- 比较可以链式书写，如 0 <= x < 10；and/or 会短路并返回最后求值的操作数，不一定返回 bool。
- == 比较值是否相等，is 比较是否为同一个对象；判断 None 应写 is None。
- in/not in 做成员测试；对 dict 测试的是键。
- 位运算作用于整数的二进制位；负整数按无限长二进制补码语义理解。
- 复杂表达式即使能靠优先级正确运行，也应使用括号表达意图。
常见误区
- 把 // 当成简单截断
- 用 is 比较数字或字符串的值
- 忘记 and 的优先级高于 or
- 连续位移、比较和逻辑运算却不加括号
适用边界
- 浮点数比较受二进制表示误差影响，需要按问题选择容差。
- 运算符可由自定义类重载，因此相同符号对不同类型可能有不同语义。
程序组织模块、导入与常用标准库正确导入模块，并按用途查找 math、random、statistics、collections、heapq、bisect 等标准工具。＋
正式定义
模块是可导入的 Python 代码单元，包把模块组织成层次。import 先加载模块并创建模块对象，再把名字绑定到当前命名空间；标准库随 Python 分发，不等于第三方包。
必须掌握
- import module 保留清晰命名空间；from module import name 只导入指定名字；避免 from module import *。
- math 提供 sqrt、floor、ceil、gcd、log、sin 等数学函数和 pi、e 等常量。
- random 用于伪随机模拟，不适合密码安全；需要安全随机时使用 secrets。
- collections.deque 适合双端队列，Counter 适合计数，defaultdict 可按工厂创建缺省值。
- heapq 实现最小堆，bisect 在已排序序列中二分定位，itertools 提供高效迭代组合工具。
- if __name__ == '__main__': 用来区分文件被直接运行还是被导入。
常见误区
- 文件名写成 math.py 导致遮蔽标准库
- import * 污染命名空间
- 把 random 当成加密随机数
- 没有理解工具的数据复杂度就盲目调用
适用边界
- 标准库非常大，本章覆盖课程会实际依赖的入口；具体函数签名应结合本站条目与运行时帮助查询。
- Turtle 需要图形窗口，本站文本判题环境不伪造其画布。
完成检查