数据结构与算法 / 系统课时

Dijkstra 算法

Dijkstra 算法

Dijkstra 算法解决非负权图的单源最短路径问题。它每次从优先队列取出当前距离最小的顶点,再松弛该顶点的出边;使用不支持减小键操作的普通堆时,还必须识别并跳过旧距离对应的过期队列项。

学习目标

  • 说明 Dijkstra 算法成立所依赖的非负权条件。
  • 使用邻接表与最小堆实现单源最短路径。
  • 理解重复入队、过期队列项和复杂度之间的关系。

核心思路

初始化时,起点距离为 0,其余顶点为正无穷。优先队列按候选距离从小到大保存 (distance, vertex)。每次弹出距离最小的记录后,检查该顶点的所有出边;若发现更短路径,就更新距离和前驱,并把新的记录压入堆。

算法正确性的关键是所有边权都非负。当前最小的有效队列项被弹出时,任何尚未处理的路径都必须先经过一个距离不小于它的顶点,再增加一个非负边权,因此不可能得到更小的距离。若存在负权边,这个结论不再成立。

Dijkstra 优先队列执行过程

过期队列项

许多标准库的堆只提供插入和弹出最小值,不直接提供对已有元素执行“减小键”。当顶点 B 的距离先从正无穷更新为 4,随后又更新为 3 时,堆中会同时存在 (4, B) 与 (3, B)。

不需要在堆中查找并删除旧记录。弹出 (4, B) 时,只要发现 4 > distance[B],即可确认它已经过期并直接跳过。该策略实现简单,并保持正确性;代价是同一顶点可能多次入队,堆的记录数在最坏情况下可达到 O(∣E∣)O(|E|)。

完整可运行示例

下面的程序先校验图中不存在负权边,再计算从 A 出发的最短距离、路径和被跳过的过期队列项数量。

python
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,然后运行:

bash
python dijkstra_demo.py

预期输出

text
最短距离: {'A': 0, 'B': 3, 'C': 1, 'D': 4}
A 到 D: A -> C -> B -> D
跳过的过期队列项: 2

B 先以距离 4 入队,后来被路径 A -> C -> B 改进为 3;D 也先以 6 入队,随后改进为 4。因此,旧记录 (4, B) 与 (6, D) 被弹出时都会命中过期判断。

复杂度与边界

使用邻接表和二叉最小堆时,每次成功松弛最多新增一个队列项,时间复杂度为 O((∣V∣+∣E∣)log⁡∣V∣)O((|V|+|E|)\log |V|),常写作 O(∣E∣log⁡∣V∣)O(|E|\log |V|);图本身占用 O(∣V∣+∣E∣)O(|V|+|E|) 空间,距离表和前驱表占用 O(∣V∣)O(|V|),包含过期记录的堆在最坏情况下占用 O(∣E∣)O(|E|)。

不可达顶点的距离会保持为正无穷,且不会出现在前驱表中。若只需要起点到某个终点的答案,可以在终点以有效最小记录弹出时提前结束;不能在终点第一次入队时结束,因为后续仍可能找到更短路径。

常见错误

  1. 在含负权边的图上直接运行。程序可能给出错误结果,应在执行前校验边权并改用支持负权边的算法。
  2. 弹出队列项后不检查是否过期。结果通常仍可能正确,但会重复扫描无效出边,显著增加运行时间。
  3. 使用 visited 后拒绝任何后续更新,却又没有保证首次处理的是有效最小记录。正确做法是先判断队列项是否过期,再展开邻接边。
  4. 在顶点首次入队时认定距离最终确定。入队只表示发现候选路径,只有该顶点以当前最优距离从堆顶弹出时才能确认。

本课练习

  1. 在示例图中增加边 A -> D,权重为 10。要求结果仍选择总代价 4 的路径,并观察新增候选项是否成为过期记录。
  2. 增加不可达顶点 E,输出从 A 到 E 的结果时显示“不可达”,而不是尝试拼接空路径。
  3. 为函数增加可选终点参数:当终点以有效最小记录弹出时提前结束,并用计数器比较提前结束前后弹出的队列项数量。

本课总结

  • Dijkstra 算法依赖非负边权,并以当前最小的有效距离作为贪心选择。
  • 普通最小堆无需减小键操作;发现更短距离时重新入队,弹出后跳过过期记录即可。
  • 邻接表与二叉堆实现的典型时间复杂度为 O((∣V∣+∣E∣)log⁡∣V∣)O((|V|+|E|)\log |V|),路径通过前驱表还原。

下一课预告

后续将继续比较能够处理负权边的最短路径方法,并把最短路径问题与最小生成树的目标、约束和贪心选择方式区分开来。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

Dijkstra 算法

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通