Dijkstra算法是解决非负权图单源最短路径的贪心算法，其核心是每次选未确定节点中距离最小者加入集合，并用它松弛邻接点；因依赖非负权前提，无法处理负权边。
为什么直接用 heapq 实现 Dijkstra 会出错
因为 heapq 不支持动态更新节点距离，一旦某个节点的最短距离被更新，你无法在堆中修改它已存在的条目。结果就是堆里残留过时的（更大）距离值，后续可能错误地再次弹出并重复松弛——这会导致时间浪费，甚至在有负权边时逻辑崩溃（不过 Dijkstra 本就不该用于负权图）。
常见错误现象：dist[neighbor] 已经更小了，但堆里还存着旧的 (old_dist, neighbor)，之后又被取出，导致重复处理、性能下降，或误判最短路径。
- 正确做法是「惰性删除」：每次从堆中
heappop后，先检查当前取出的距离是否等于dist[node]，不等就跳过 - 不要尝试用
heapq.heapreplace或手动遍历堆修改——堆结构不支持 O(1) 查找，这么做反而更慢且易错 - 初始化时把起点入堆：
heapq.heappush(heap, (0, start))，dist[start] = 0
邻接表怎么建才适配 heapq 版 Dijkstra
必须用字典套列表（或 defaultdict(list)），每个键是节点，值是 (neighbor, weight) 元组的列表。不能用矩阵——稠密图用邻接表+堆才是 O((V+E) log V)，矩阵则退化为 O(V²)。
示例结构：
立即学习“Python免费学习笔记（深入）”；
graph = {
'A': [('B', 4), ('C', 2)],
'B': [('C', 1), ('D', 5)],
'C': [('D', 8)],
'D': []
}
- 节点名可以是字符串、整数，但必须可哈希；如果用索引整数（0~n-1），
dist用列表更高效 - 权重必须非负，否则算法不保证正确——这不是实现问题，是 Dijkstra 的数学前提
- 如果图含孤立节点，确保它们出现在
graph键中或单独初始化进dist，否则可能漏掉
dist 初始化和松弛逻辑的关键细节
dist 必须初始化为无穷大（float('inf')），起点为 0。松弛时只在 new_dist < dist[neighbor] 成立时更新，并立即入堆——即使堆里已有旧值也没关系，靠惰性删除过滤。
- 别用
math.inf（Python 3.5+ 虽支持，但float('inf')更通用、显式） - 松弛后必须
heappush(heap, (new_dist, neighbor))，不能省略——这是保证所有潜在更优路径都被考虑的前提 - 如果只需单源到单目标，可在
node == target时直接return dist[node]，不必跑完全部 - 若需路径本身，额外维护
prev字典记录前驱节点，最后逆推即可
遇到 “IndexError: list index out of range” 或 “KeyError” 怎么快速定位
这两类错误几乎都源于图结构和 dist / 节点索引没对齐。比如用整数 0~n-1 当节点，但 graph 缺少某节点键，或 dist 列表长度不够。
- 检查输入图是否覆盖所有涉及节点：遍历
graph的键和所有邻接项，确认没有未声明的节点 - 如果用列表存
dist，确保len(dist) >= max_node_id + 1；若用字典，初始化所有可能节点键，或改用defaultdict(lambda: float('inf')) - 打印堆顶元素和当前
dist[node]对比，能立刻发现是否因节点名类型不一致（如字符串 '0' 和整数 0）导致匹配失败
最常被忽略的是：图输入含重边时，邻接表里要保留所有边（哪怕权重不同），不能去重——Dijkstra 会自己选最小的那条。
