无向图的单源最短路径问题（Dijkstra算法）

我将为您详细讲解图论中的经典算法——Dijkstra算法，它用于解决无负权边的带权无向图的单源最短路径问题。

问题描述

给定一个带权无向图G=(V,E)，其中每条边e∈E都有一个非负的权重w(e)≥0，以及一个源顶点s∈V。目标是找到从源点s到图中所有其他顶点的最短路径长度。

核心思想

Dijkstra算法采用贪心策略，逐步确定从源点s到各顶点的最短距离。算法维护一个集合S，包含已经确定最短距离的顶点。在每一步中，选择距离s最近的未处理顶点加入S，并更新其邻居的距离。

算法步骤详解

步骤1：初始化

• 创建距离数组dist[]，其中dist[v]表示当前已知的从s到v的最短距离估计值
  • dist[s] = 0（源点到自身的距离为0）
  • 对于所有v≠s，dist[v] = ∞（初始时未知距离）
• 创建前驱数组prev[]记录路径（可选）
• 创建集合S = ∅（已确定最短距离的顶点集合）
• 创建优先队列Q，包含所有顶点，按dist值排序

步骤2：主循环

当优先队列Q不为空时重复以下过程：

1. 提取最小顶点：从Q中取出dist值最小的顶点u（即当前距离s最近的未处理顶点）
2. 标记为已处理：将u加入集合S，此时dist[u]就是s到u的最终最短距离
3. 松弛操作：检查u的所有邻居顶点v
   • 对于每个邻居v，如果v∉S且存在更短路径：
     • 计算新距离：new_dist = dist[u] + w(u,v)
     • 如果new_dist < dist[v]：
       • 更新dist[v] = new_dist
       • 更新prev[v] = u（记录路径）
       • 调整优先队列中v的位置

步骤3：输出结果

算法结束后，dist[]数组包含s到所有顶点的最短距离，prev[]数组可用于重构具体路径。

详细示例演示

考虑以下无向图（顶点A为源点）：

    A
   / \
  2   4
 /     \
B---3---C
 \     /
  1   2
   \ /
    D

执行过程：

初始化：

• dist[A]=0, dist[B]=∞, dist[C]=∞, dist[D]=∞
• S = ∅
• Q = [A(0), B(∞), C(∞), D(∞)]

第1次迭代：

• 取出A(0)，加入S={A}
• 更新邻居：
  • B: dist[B] = min(∞, 0+2) = 2
  • C: dist[C] = min(∞, 0+4) = 4
• Q = [B(2), C(4), D(∞)]

第2次迭代：

• 取出B(2)，加入S={A,B}
• 更新邻居：
  • C: dist[C] = min(4, 2+3) = 4（不变）
  • D: dist[D] = min(∞, 2+1) = 3
• Q = [D(3), C(4)]

第3次迭代：

• 取出D(3)，加入S={A,B,D}
• 更新邻居：
  • C: dist[C] = min(4, 3+2) = 4（不变）
• Q = [C(4)]

第4次迭代：

• 取出C(4)，加入S={A,B,C,D}
• Q = ∅

最终结果：

• dist[A]=0, dist[B]=2, dist[C]=4, dist[D]=3

算法复杂度分析

• 时间复杂度：
  • 使用二叉堆优先队列：O((V+E)logV)
  • 使用斐波那契堆：O(E + VlogV)（最优）
• 空间复杂度：O(V+E)

关键特性与注意事项

1. 非负权重要求：如果图中存在负权边，Dijkstra算法可能得到错误结果
2. 贪心正确性证明：基于非负权重假设，局部最优选择可保证全局最优
3. 应用场景：路由算法、地图导航、网络优化等
4. 变体改进：可使用双向Dijkstra、A*算法等优化特定场景

通过这种逐步扩展的方式，Dijkstra算法能够高效且正确地找到无负权图中的最短路径，是图论中最基础且重要的算法之一。