Dijkstra 最短路径：贪心与优先队列优化

Dijkstra 最短路径算法：贪心与优先队列优化

Dijkstra 算法是一种经典的单源最短路径算法，用于计算图中一个起始节点到所有其他节点的最短距离。它的核心思想是贪心策略：每次从未确定最短距离的节点中，选择当前距离最小的节点，并尝试用它的边去更新相邻节点的距离。引入**优先队列（最小堆）**后，算法可以达到 (O((V+E)\log V)) 的时间复杂度。

本文将在无负权边的前提下，带你从贪心思路出发，逐步构建基础实现，再优化为堆优化版本，并结合图示实例彻底理解 Dijkstra。

算法核心：贪心与松弛操作

Dijkstra 算法基于以下两个关键操作：

• 贪心选择：维护一个集合，存放“已确定最短距离”的节点。每次从尚未确定的节点中，挑出一个距离源点最近的节点，将其标记为“已确定”。这是因为在边权非负的图中，这个当前最小的距离不会再被其他路径缩短（任何绕路都会增加代价）。
• 松弛（Relaxation）：当确定一个节点 (u) 的最短距离后，遍历所有从 (u) 出发的边 (u \to v)（权值 (w)），若 dist[u] + w < dist[v]，则更新 dist[v] 为更小的值。

重复上述过程，直到所有节点的最短距离都被确定。

图解实例

以下图为例，求从节点 A 到其余各点的最短路径：

       (1)       (4)
  A ------- B ------- D
  |         |         |
(2)       (3)       (1)
  |         |         |
  +------ C ---------+

1. 初始化：dist[A]=0，其他节点距离为 (\infty)。未确定集合 (Q = {A,B,C,D})。
2. 选择最小 dist 的节点 A(0)。标记 A 为已确定，松弛 A 的邻边：
   • A→B (1): dist[B] 从 ∞ 更新为 0+1=1
   • A→C (2): dist[C] 从 ∞ 更新为 0+2=2
3. 未确定节点中最小：B(1)。标记 B 为已确定，松弛 B 的邻边：
   • B→D (4): dist[D] 更新为 1+4=5
   • B→C (3): 1+3=4，但当前 dist[C]=2，不更新（保留更小的2）
4. 最小未确定节点：C(2)。松弛 C 的邻边：
   • C→D (1): dist[D] 当前5，2+1=3 < 5，更新 dist[D]=3
5. 最后选择 D(3)。没有出边（或松弛后无变化）。
6. 最终 dist：A:0, B:1, C:2, D:3。

贪心选择保证了每次确定的节点距离都是全局最短。

基础实现：朴素 O(V²)

直接使用线性搜索在未确定节点中找最小 dist 值。

def dijkstra_naive(graph, start):
    n = len(graph)
    dist = [float('inf')] * n
    visited = [False] * n
    dist[start] = 0

    for _ in range(n):
        # 寻找未访问节点中距离最小的节点
        u = -1
        min_dist = float('inf')
        for i in range(n):
            if not visited[i] and dist[i] < min_dist:
                min_dist = dist[i]
                u = i
        if u == -1:    # 剩余节点不可达
            break
        visited[u] = True

        # 松弛邻接边
        for v, weight in graph[u]:
            if not visited[v] and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
    return dist

• 时间复杂度：(O(V^2))，适用于稠密图。
• 缺点：每次寻找全局最小节点需要遍历所有 V，效率较低。

优先队列优化：O((V+E)log V)

使用最小堆（heapq）直接获取最小距离节点，避免暴力搜索。

关键点：堆中可能存有同一节点多个不同的距离记录（旧值），取出时需判断该节点是否已确定最短距离；若已确定，则跳过该“过期”记录。

import heapq

def dijkstra_heap(graph, start):
    n = len(graph)
    dist = [float('inf')] * n
    dist[start] = 0
    # 堆中存储 (当前距离, 节点)，Python 默认按第一元素排序
    pq = [(0, start)]
    visited = [False] * n

    while pq:
        cur_dist, u = heapq.heappop(pq)
        if visited[u]:
            continue    # 该记录已过期，跳过
        visited[u] = True

        for v, weight in graph[u]:
            if cur_dist + weight < dist[v]:
                dist[v] = cur_dist + weight
                heapq.heappush(pq, (dist[v], v))
    return dist

复杂度分析：

• 每个节点最多入堆一次（但可能多次 heappush），边也可能导致多次压入，总压入次数 (O(E))。
• 每次堆操作 (O(\log V))，总时间 (O((V+E)\log V))，稀疏图下显著优于朴素版。

处理负权边？Dijkstra 的局限性

Dijkstra 算法要求所有边的权值非负。若图中存在负权边，贪心的前提——“已确定节点的距离不会再次被缩短”将被打破，可能导致错误结果。负权图请使用 Bellman-Ford 或 SPFA 算法。

常见变体与应用

• 记录最短路径：在松弛成功时，同时记录前驱节点 prev[v] = u，最后反推路径。
• 多目标最短路径：可运行到所有节点，也可提前终止于目标节点（弹出目标节点时停止）。
• 双向 Dijkstra：从起点和终点同时运行，减少搜索空间，常用于地图导航。
• A* 算法：在 Dijkstra 基础上引入启发式函数，加速目标导向搜索。

总结对比

Dijkstra 以清晰的贪心逻辑和高效的堆优化，成为图论中必学必用的基石算法。理解其“确定性”与“松弛”的本质，能帮助你解决大量最小代价路径类问题。

练习题推荐

1. LeetCode 743. 网络延迟时间：经典 Dijkstra 判断信号到达所有节点的时间。
2. LeetCode 1514. 概率最大的路径：求最大概率路径，可将权值取负对数转化为最短路径。
3. POJ 2387 / 洛谷 P3371：标准模板题，验证朴素与堆优化实现。