Dijkstra算法求单源最短路径问题 题目描述 给定一个带权有向图G=(V,E)，其中每条边e∈E都有一个非负权重w(e)≥0，以及一个源顶点s∈V。我们需要找到从源点s到图中所有其他顶点v∈V的最短路径距离。最短路径距离δ(s,v)定义为从s到v的所有路径中，边上权重之和最小的那条路径的权重和。 解题过程 Dijkstra算法是解决带非负权边的图单源最短路径问题的经典贪心算法。其核心思想是维护一个顶点集合S，该集合包含已经找到最短路径的顶点。算法反复从集合V-S（即尚未确定最短路径的顶点集合）中选取一个距离源点s最近的顶点u，将其加入S，然后对u的所有出边进行松弛操作，更新其邻居顶点的当前最短距离估计值。 步骤详解 初始化 创建一个数组 dist ，大小为|V|，用于存储从源点s到每个顶点v的当前最短距离估计值。 设置 dist[s] = 0 。 对于所有v∈V且v≠s，设置 dist[v] = ∞ （在编程中通常用一个非常大的数表示）。 创建一个集合 S （或一个布尔数组 visited ），用于记录哪些顶点的最短距离已经被最终确定。初始时， S 为空。 （可选）创建一个数组 prev ，用于记录最短路径树中每个顶点的前驱顶点，以便重构具体路径。 主循环 当集合 S 尚未包含所有顶点（即 V-S 不为空）时，重复以下步骤： a. 选择未确定顶点中的最小估计值顶点 * 从尚未加入 S 的顶点集合（V-S）中，选择一个当前 dist[u] 值最小的顶点u。 * 顶点u此时的性质是：它的 dist[u] 就是从s到u的最短路径距离。为什么？因为所有边的权重都是非负的，如果我们从s出发，试图通过其他尚未确定的顶点（V-S中的点）绕道到达u，那么这条绕道路径的长度至少是 dist[u] （因为u已经是V-S中距离s最近的点），加上非负的边权，总距离不会比 dist[u] 更小。因此， dist[u] 就是最终的最短距离。 b. 将顶点u加入集合S * 将顶点u标记为“已确定”，将其加入集合 S 。这意味着从s到u的最短距离已经找到。 c. 松弛操作 * 遍历顶点u的所有出边。对于每一条边(u, v)，其中v是u的邻居顶点。 * 检查是否存在一条通过u到达v的、更短的路径。具体方法是计算： new_dist = dist[u] + w(u, v) ，其中 w(u, v) 是边(u, v)的权重。 * 如果 new_dist 小于v当前的估计值 dist[v] ，则更新 dist[v] 为 new_dist 。这表示我们发现了一条从s到v的、更短的路径（该路径是先到u，再走边(u, v)）。 * 同时，更新v的前驱顶点为u（如果使用了 prev 数组）。 算法终止 当所有顶点都已被加入 S 时，算法终止。此时，数组 dist 中存储的就是从源点s到每个顶点的最短路径距离。 关键点与示例 贪心选择性质 ：每一步都选择当前“最近”的未确定顶点，这个选择是安全的（基于非负权重的假设）。 非负权重的重要性 ：如果图中存在负权边，上述的“贪心选择是安全的”这一性质将不再成立。因为可能存在一条路径，通过一个负权边，使得绕道走的距离反而比当前已知的最小距离更短。对于含负权边的图，需要使用Bellman-Ford算法。 数据结构优化 ：上述步骤中，寻找最小 dist 值的顶点u是性能关键。如果使用简单的线性搜索，算法复杂度为O(|V|²)。通常使用 最小堆（优先队列） 来高效地实现这个选择操作，可以将复杂度优化到O((|V| + |E|) log |V|)。 举例说明 考虑一个简单的图，顶点集为{A, B, C, D, E}，源点为A。边及其权重如下：A->B:4, A->C:2, B->C:1, B->D:5, C->B:1, C->D:8, C->E:10, D->E:2。 执行过程如下表（假设使用优先队列）： | 步骤 | 已确定集合 S | 当前dist值 (A,B,C,D,E) | 选择的顶点u (V-S中dist最小) | 松弛操作 (更新邻居的dist) | | :--- | :--- | :--- | :--- | :--- | | 初始化 | {} | (0, ∞, ∞, ∞, ∞) | - | - | | 1 | {} | (0, ∞, ∞, ∞, ∞) | A (dist=0) | 松弛A的邻居： B: 0+4=4 < ∞, 更新dist[ B]=4 C: 0+2=2 < ∞, 更新dist[ C ]=2 | | 2 | {A} | (0, 4, 2, ∞, ∞) | C (dist=2) | 松弛C的邻居： B: 2+1=3 < 4, 更新dist[ B]=3 D: 2+8=10 < ∞, 更新dist[ D]=10 E: 2+10=12 < ∞, 更新dist[ E ]=12 | | 3 | {A, C} | (0, 3, 2, 10, 12) | B (dist=3) | 松弛B的邻居： D: 3+5=8 < 10, 更新dist[ D]=8 (C已确定，无需再更新) | | 4 | {A, C, B} | (0, 3, 2, 8, 12) | D (dist=8) | 松弛D的邻居： E: 8+2=10 < 12, 更新dist[ E ]=10 | | 5 | {A, C, B, D} | (0, 3, 2, 8, 10) | E (dist=10) | E无出边（或邻居已确定） | | 结束 | {A, B, C, D, E} | (0, 3, 2, 8, 10) | - | - | 最终结果：从A到各点的最短距离为 A:0, B:3, C:2, D:8, E:10。