带权最短路寻找边权总和最小的路径。松弛是一条基本操作：若已有到 u 的代价，再走 u→v 比当前记录更便宜，就降低 v 的距离。算法之间的差异主要在于按什么顺序做松弛，以及何时能确认结果不再改变。
Dijkstra为什么要求非负权
当未确定顶点里距离最小的 u 被取出时，若所有后续边非负，经由其他尚未确定节点绕一圈也不可能把它降得更低，因此可确定它的最短距离。这一步证明依赖非负权；出现负边后，未来的更长前缀可能被负权抵消，原结论失效。
import heapq
import itertools
import math
def dijkstra(graph, source):
nodes = set(graph)
for edges in graph.values():
for target, weight in edges:
if not math.isfinite(weight) or weight < 0:
raise ValueError('weights must be finite and non-negative')
nodes.add(target)
if source not in nodes:
raise ValueError('unknown source')
distance = {node: math.inf for node in nodes}
distance[source] = 0
sequence = itertools.count()
heap = [(0, next(sequence), source)]
while heap:
cost, _, vertex = heapq.heappop(heap)
if cost != distance[vertex]:
continue
for target, weight in graph.get(vertex, ()):
candidate = cost + weight
if candidate < distance[target]:
distance[target] = candidate
heapq.heappush(heap, (candidate, next(sequence), target))
return distance
if __name__ == '__main__':
graph = {'a': [('b', 4), ('c', 1)], 'c': [('b', 1)], 'b': [], 'x': []}
print(dijkstra(graph, 'a'))
例子中 a→b 成本4，而 a→c→b 成本2；优先队列帮助先处理更有希望的候选。Python堆不提供按顶点直接降低键的接口，代码把新距离作为新条目压入；弹出时若该距离已经不是当前最优记录，就跳过过期条目。
堆条目加递增编号，防止同距离时继续比较任意顶点对象。所有边在开始时检查为非负有限数，包括不可达分量，输入不满足规格时立即拒绝。用无穷表示不可达，浮点NaN则会破坏比较关系，所以不允许作为边权。
在可能有平行边的邻接表中，这种懒删除实现最多加入 O(E) 条目，时间可记为 O((V+E) log(V+E))，额外空间 O(V+E)。简单图里常简写成 O((V+E) log V)。这与支持真正减键的堆实现不能不加区分地混报。
负边、所有点对与启发式
Bellman–Ford反复遍历全部边。没有可达负环时，最短简单路径最多 V-1 条边，所以做 V-1 轮后答案稳定；再能松弛说明存在从源点可达的负环，相关路径可能没有有限最小值。它的典型成本 O(VE)。
DAG可以先拓扑排序，再按顺序松弛，即使有负边也可在线性时间处理。所有点对最短路可用 Floyd–Warshall 的中间点DP，时间 O(V³)、空间 O(V²)，适合中小规模稠密图；稀疏图可考虑多次单源算法或Johnson重赋权，仍要满足相应前提。
A*用 g+h 决定探索优先级。启发式若高估实际剩余成本，可能错过最优路径；是否允许重新打开节点，还与一致性条件及实现方式有关。机器人中的障碍物、动态场景与运动约束需要在通用图模型之外另外建模。
练习与面试自查
给Dijkstra增加父指针并恢复路径，检查恢复后边权和等于返回距离。构造含零权边、重边、不连通分量和等长路径的图，再与小图上的Floyd–Warshall对拍。另画一个带负边的例子，指出贪心确定步骤在哪一刻失去证明。
面试时应能解释：为什么BFS只适合等权边；过期堆条目为何可以直接丢弃；“图里存在负环”与“该负环从源点可达”有什么区别。最短路径树与最小生成树的优化目标也不同。
本地运行
示例仅使用 Python 标准库，适用于 Python 3.10 及以上。把 example.py 与 test_example.py 保存到同一个目录，在该目录运行：
python example.py
python -m unittest -v test_example.py
测试检查本文列出的边界；新增练习仍需自己补充断言。