数据结构与算法 / 系统课时
Dijkstra 算法
Dijkstra 算法
Dijkstra 算法解决非负权图的单源最短路径问题。它每次从优先队列取出当前距离最小的顶点,再松弛该顶点的出边;使用不支持减小键操作的普通堆时,还必须识别并跳过旧距离对应的过期队列项。
学习目标
- 说明 Dijkstra 算法成立所依赖的非负权条件。
- 使用邻接表与最小堆实现单源最短路径。
- 理解重复入队、过期队列项和复杂度之间的关系。
核心思路
初始化时,起点距离为 0,其余顶点为正无穷。优先队列按候选距离从小到大保存 (distance, vertex)。每次弹出距离最小的记录后,检查该顶点的所有出边;若发现更短路径,就更新距离和前驱,并把新的记录压入堆。
算法正确性的关键是所有边权都非负。当前最小的有效队列项被弹出时,任何尚未处理的路径都必须先经过一个距离不小于它的顶点,再增加一个非负边权,因此不可能得到更小的距离。若存在负权边,这个结论不再成立。

过期队列项
许多标准库的堆只提供插入和弹出最小值,不直接提供对已有元素执行“减小键”。当顶点 B 的距离先从正无穷更新为 4,随后又更新为 3 时,堆中会同时存在 (4, B) 与 (3, B)。
不需要在堆中查找并删除旧记录。弹出 (4, B) 时,只要发现 4 > distance[B],即可确认它已经过期并直接跳过。该策略实现简单,并保持正确性;代价是同一顶点可能多次入队,堆的记录数在最坏情况下可达到 。
完整可运行示例
下面的程序先校验图中不存在负权边,再计算从 A 出发的最短距离、路径和被跳过的过期队列项数量。
import heapq
def dijkstra(graph, start):
if start not in graph:
raise ValueError("起点不在图中")
# Dijkstra 的正确性要求所有边权非负,且邻接点必须有定义。
for node, neighbors in graph.items():
for neighbor, weight in neighbors:
if neighbor not in graph:
raise ValueError(f"节点 {neighbor} 缺少邻接表")
if weight < 0:
raise ValueError("Dijkstra 算法不接受负权边")
distance = {node: float("inf") for node in graph}
previous = {start: None}
distance[start] = 0
queue = [(0, start)]
stale_items = 0
while queue:
current_distance, node = heapq.heappop(queue)
# 同一节点可能多次入队,只处理与当前最优距离一致的记录。
if current_distance > distance[node]:
stale_items += 1
continue
for neighbor, weight in graph[node]:
candidate = current_distance + weight
if candidate < distance[neighbor]:
distance[neighbor] = candidate
previous[neighbor] = node
heapq.heappush(queue, (candidate, neighbor))
return distance, previous, stale_items
def rebuild_path(previous, target):
if target not in previous:
return []
path = []
current = target
while current is not None:
path.append(current)
current = previous[current]
path.reverse()
return path
def main():
graph = {
"A": [("B", 4), ("C", 1)],
"B": [("D", 1)],
"C": [("B", 2), ("D", 5)],
"D": [],
}
distance, previous, stale_items = dijkstra(graph, "A")
print("最短距离:", distance)
print("A 到 D:", " -> ".join(rebuild_path(previous, "D")))
print("跳过的过期队列项:", stale_items)
if __name__ == "__main__":
main()将代码保存为 dijkstra_demo.py,然后运行:
python dijkstra_demo.py预期输出
最短距离: {'A': 0, 'B': 3, 'C': 1, 'D': 4}
A 到 D: A -> C -> B -> D
跳过的过期队列项: 2B 先以距离 4 入队,后来被路径 A -> C -> B 改进为 3;D 也先以 6 入队,随后改进为 4。因此,旧记录 (4, B) 与 (6, D) 被弹出时都会命中过期判断。
复杂度与边界
使用邻接表和二叉最小堆时,每次成功松弛最多新增一个队列项,时间复杂度为 ,常写作 ;图本身占用 空间,距离表和前驱表占用 ,包含过期记录的堆在最坏情况下占用 。
不可达顶点的距离会保持为正无穷,且不会出现在前驱表中。若只需要起点到某个终点的答案,可以在终点以有效最小记录弹出时提前结束;不能在终点第一次入队时结束,因为后续仍可能找到更短路径。
常见错误
- 在含负权边的图上直接运行。程序可能给出错误结果,应在执行前校验边权并改用支持负权边的算法。
- 弹出队列项后不检查是否过期。结果通常仍可能正确,但会重复扫描无效出边,显著增加运行时间。
- 使用
visited后拒绝任何后续更新,却又没有保证首次处理的是有效最小记录。正确做法是先判断队列项是否过期,再展开邻接边。 - 在顶点首次入队时认定距离最终确定。入队只表示发现候选路径,只有该顶点以当前最优距离从堆顶弹出时才能确认。
本课练习
- 在示例图中增加边
A -> D,权重为 10。要求结果仍选择总代价 4 的路径,并观察新增候选项是否成为过期记录。 - 增加不可达顶点
E,输出从A到E的结果时显示“不可达”,而不是尝试拼接空路径。 - 为函数增加可选终点参数:当终点以有效最小记录弹出时提前结束,并用计数器比较提前结束前后弹出的队列项数量。
本课总结
- Dijkstra 算法依赖非负边权,并以当前最小的有效距离作为贪心选择。
- 普通最小堆无需减小键操作;发现更短距离时重新入队,弹出后跳过过期记录即可。
- 邻接表与二叉堆实现的典型时间复杂度为 ,路径通过前驱表还原。
下一课预告
后续将继续比较能够处理负权边的最短路径方法,并把最短路径问题与最小生成树的目标、约束和贪心选择方式区分开来。