题目描述

给定一个有向带权图，求从起点到所有其他节点的最短路径长度。图中可能存在重边和自环，边权为正数。

Dijkstra 算法适用于所有边权非负的图。堆优化版本通过优先队列（最小堆）快速取出当前距离最小的未确定节点，在简单图的常见分析中，时间复杂度可写为 O((V + E)log V)；允许任意重边时，应使用下文针对惰性堆的界。

解题方法：Dijkstra + 堆优化

算法思路

维护一个距离数组 dist，初始时起点距离为 0，其余为无穷大。用最小堆存储 (距离, 节点)，每次取出堆顶距离最小的节点，如果该距离已经大于 dist[u] 则跳过（惰性删除），否则遍历其所有邻边尝试松弛。

松弛成功时将新距离入堆。重复此过程直到堆为空。

代码解析

import heapq

def dijkstra(graph, start, n):
    """
    graph: 邻接表 {u: [(v, w), ...]}
    start: 起点，满足 0 <= start < n
    n: 总顶点数，顶点编号为 0..n-1；所有边权非负
    无出边的顶点可以不作为 graph 的键
    返回: 起点到所有点的最短距离
    """
    dist = [float('inf')] * n
    dist[start] = 0
    pq = [(0, start)]

    while pq:
        d, u = heapq.heappop(pq)
        # 如果当前距离大于已记录的最短距离，跳过
        if d > dist[u]:
            continue
        for v, w in graph.get(u, []):
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist


# 顶点 1 无出边，顶点 2 为孤立点
graph = {0: [(1, 1)]}
print(dijkstra(graph, 0, 3))  # [0, 1, inf]

代码要点说明

  • dist 数组：记录起点到每个节点的当前最短距离，初始化为无穷大。
  • 优先队列 pq：以 (距离, 节点) 形式存储，Python 的 heapq 默认按第一个元素排序。
  • 惰性删除：if d > dist[u]: continue 用于跳过已经过期的堆元素。节点可能被多次入堆，但只有距离最小的那次才有效。
  • 松弛操作：如果通过 u 到达 v 的距离 d + w 比当前记录 dist[v] 更短，则更新并重新入堆。

复杂度分析

  • 时间复杂度：O(V + E log(E+2))。每条边最多触发一次成功松弛，但同一节点可以多次入堆；惰性堆最多保留 O(E) 条记录。在简单图下，也常写为 O((V+E)log V)。
  • 空间复杂度：O(V+E)。距离数组为 O(V)，堆最坏为 O(E)；若计入邻接表，整体仍为 O(V+E)。