直接用 heapq 实现 dijkstra 可能算错最短距离，因 heapq 不支持动态更新权重，旧条目残留导致重复松弛；必须在出堆时检查 dist[u] 是否过期，即 if d > dist[u]: continue。
为什么直接用 heapq 实现 Dijkstra 会算错最短距离？
因为 Python 的 heapq 不支持动态更新节点权重，旧的过时条目仍留在堆里，导致同一个节点被重复松弛、甚至误判为更短路径。
典型现象是：图中存在负权边时结果异常（但注意——Dijkstra 本就不该用于负权图）；更常见的是，某节点首次出堆后又被更低距离“唤醒”，而你没做去重判断。
- 必须在节点出堆时检查其距离是否已过期：
if dist[node] != current_dist: continue - 初始化
dist用float('inf')，起点设为0 - 邻接表推荐用
dict套list[tuple[neighbor, weight]]，别用嵌套dict增加查找开销
怎么写一个能跑通的 Dijkstra + heapq 最小堆？
核心就三步：建图、初始化距离数组、循环弹堆+松弛。不需要封装类，函数内联写反而更清晰。
示例场景：无向图，节点编号从 0 到 n-1，求从 start 到 end 的最短距离
import heapq
<p>def dijkstra(graph, start, end):
n = len(graph)
dist = [float('inf')] * n
dist[start] = 0
heap = [(0, start)]</p><pre class="brush:python;toolbar:false;">while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: # 过期条目，跳过
continue
if u == end:
return d
for v, w in graph[u]:
new_dist = d + w
if new_dist
heapq 和 queue.PriorityQueue 能混用吗？
不能。它们底层行为不一致：PriorityQueue 是线程安全封装，内部用 heapq，但不暴露底层堆列表，也没法做「跳过过期条目」的关键判断。
常见错误是把 PriorityQueue.put((dist, node)) 和 get() 当成等价替代，结果无法校验当前取出的距离是否最新。
- 坚持用
heapq+ 元组(distance, node)形式 - 避免在堆里存可变对象（如字典或自定义类），否则排序可能出错
- 如果距离相同，建议补上
node作为第二排序键，防止比较失败：(dist, node)
稀疏图和稠密图对实现有啥实际影响？
Python 里几乎只用邻接表（list of list 或 dict），不用邻接矩阵——后者在 n > 1000 时内存暴涨且遍历慢。
真正要注意的是：当边数接近 n²（比如网格图、全连通小图），堆操作频次高，但每次 heappush 开销小；而频繁的 dist[v] 判断本身成本很低，不必优化。
- 别手动实现斐波那契堆——Python 没必要，也没人维护
- 如果图固定且查询极多，考虑预计算所有点对（Floyd-Warshall），但那是另一回事了
- 真实项目中，优先用
networkx.dijkstra_path_length，除非你明确卡在性能或依赖上
Dijkstra 的边界其实很窄：它要求非负权、单源、静态图。一旦出现边权实时变化、要查第 k 短路、或者带资源约束（比如电量限制），就得换思路——这时候堆还是那个堆，但算法逻辑已经不是 Dijkstra 了。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
