题目描述

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

Dijkstra 算法适用于所有边权非负的图。堆优化版本通过优先队列（最小堆）快速取出当前距离最小的未确定节点，将时间复杂度从 O(V²) 优化到 O((V + E)log V)。

解题方法：Dijkstra + 堆优化

算法思路

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

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

代码解析

import heapq

def dijkstra(graph, start):
    """
    graph: 邻接表 {u: [(v, w), ...]}
    start: 起点
    返回: 起点到所有点的最短距离
    """
    n = len(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[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

代码要点说明

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

复杂度分析

  • 时间复杂度：O((V + E)log V)，每个节点最多入堆一次，每条边被松弛一次，每次堆操作 O(log V)。
  • 空间复杂度：O(V)，dist 数组和堆各占用 O(V) 空间。