Dijkstra算法原理与实现
字数 3383 2025-11-15 23:12:34

Dijkstra算法原理与实现

Dijkstra算法是解决单源最短路径问题的经典算法，由荷兰计算机科学家Edsger Dijkstra于1956年提出。它用于在带非负权重的有向图或无向图中，找到一个顶点（称为源点）到其他所有顶点的最短路径。

问题描述与核心思想

问题描述：给定一个图 G=(V, E)，其中 V 是顶点集合，E 是边集合。每条边 e = (u, v) 都有一个非负的权重 w(u, v)。给定一个源顶点 s，我们需要找出从 s 到图中每一个其他顶点 v 的最短路径距离。

核心思想：Dijkstra算法采用了一种贪心策略。它维护一个集合 S，这个集合包含所有已经找到从源点 s 出发的最短路径的顶点。算法反复从尚未确定最短路径的顶点集合（V-S）中，选择一个当前距离 s 最近的顶点 u，将其加入 S，然后对 u 的所有邻居顶点进行“松弛”操作。这个“最近”的判断是基于当前已知的、但不一定是最终的最短距离估计值。

可以通俗地理解为“多米诺骨牌”效应：一旦一个顶点的最短距离被最终确定，我们就可以放心地利用这个确定无疑的信息，去更新它所能影响到的周围邻居的距离估计。

算法步骤详解

我们用一个例子来逐步讲解。考虑以下有向图，源点为顶点 A。边上的数字代表权重。

    A --1--> B --2--> D
     \      |        ^
      \4    |1       |2
       \    v        |
        -> C --3--> E

步骤1：初始化

我们需要两个关键的数据结构：

  1. dist：一个数组（或字典），用于记录从源点 s 到每个顶点 v 的当前最短距离估计值。
    • 初始化：dist[s] = 0（源点到自己的距离为0），对于其他所有顶点 v，dist[v] = ∞（无穷大，表示尚未知）。
  2. visited（或集合 S）：一个集合，用于记录哪些顶点的最短距离已经被最终确定。
    • 初始化：visited 为空集。

另一种常见且高效的做法是使用一个优先队列（最小堆） 来替代 visited 集合和遍历查找最小 dist 的过程。优先队列中存储 (当前距离估计值, 顶点) 对，并总是让距离最小的顶点出队。下面的讲解将采用这种更优的实现方式。

初始化结果：

  • dist: { A:0, B:∞, C:∞, D:∞, E:∞ }
  • 优先队列（最小堆）: [(0, A)] （初始时只有源点 A）

步骤2：循环处理，直到优先队列为空

第一次循环：

  • 出队：从优先队列中弹出距离最小的顶点，即顶点 A（dist[A] = 0）。
  • 检查邻居：顶点 A 有两个邻居：B 和 C。
  • 松弛操作：对于每个邻居顶点 v，检查如果通过当前顶点 u（即 A）到达 v，能否得到一条比当前已知路径更短的路径。即，判断 dist[u] + w(u, v) < dist[v] 是否成立。
    • 对于邻居 B：dist[A] + w(A, B) = 0 + 1 = 1。1 < ∞ 成立。因此更新 dist[B] = 1。同时，将 (1, B) 加入优先队列。
    • 对于邻居 C：dist[A] + w(A, C) = 0 + 4 = 4。4 < ∞ 成立。因此更新 dist[C] = 4。同时，将 (4, C) 加入优先队列。
  • 此时，顶点 A 的最短距离被确定为 0。
  • 当前状态：
    • dist: { A:0, B:1, C:4, D:∞, E:∞ }
    • 优先队列: [(1, B), (4, C)]

第二次循环：

  • 出队：弹出距离最小的顶点 B（dist[B] = 1）。
  • 检查邻居：顶点 B 有两个邻居：D 和 C。
  • 松弛操作：
    • 对于邻居 D：dist[B] + w(B, D) = 1 + 2 = 3。3 < ∞ 成立。更新 dist[D] = 3。将 (3, D) 入队。
    • 对于邻居 C：dist[B] + w(B, C) = 1 + 1 = 2。2 < 4（当前 dist[C] 的值）成立。这是一个关键步骤！我们发现了一条从 A 经 B 到 C 的更短路径（长度为2），优于之前直接 A->C 的路径（长度为4）。因此更新 dist[C] = 2。注意，我们需要将新的、更短的距离 (2, C) 加入优先队列。此时队列中会有两个关于 C 的条目 (2, C) 和 (4, C)，但这没关系，当我们弹出 (4, C) 时，因为 C 已经被处理过（其 dist 已经变得更小），我们可以直接忽略这个陈旧的条目。
  • 当前状态：
    • dist: { A:0, B:1, C:2, D:3, E:∞ }
    • 优先队列: [(2, C), (3, D), (4, C)] （注意队列中有两个 C）

第三次循环：

  • 出队：弹出距离最小的顶点 C（dist[C] = 2）。注意，即使队列中还有一个 (4, C)，但我们先处理的是更小的 (2, C)。
  • 检查邻居：顶点 C 有一个邻居：E。
  • 松弛操作：
    • 对于邻居 E：dist[C] + w(C, E) = 2 + 3 = 5。5 < ∞ 成立。更新 dist[E] = 5。将 (5, E) 入队。
  • 当前状态：
    • dist: { A:0, B:1, C:2, D:3, E:5 }
    • 优先队列: [(3, D), (4, C), (5, E)]

第四次循环：

  • 出队：弹出顶点 D（dist[D] = 3）。
  • 检查邻居：顶点 D 没有出边（邻居）。
  • 松弛操作：无。
  • 当前状态：
    • dist: { A:0, B:1, C:2, D:3, E:5 }
    • 优先队列: [(4, C), (5, E)]

第五次循环：

  • 出队：弹出顶点 C（dist[C] = 4）。但是，当我们检查当前记录时，发现 dist[C] 已经是 2（小于4）。这意味着我们弹出的这个 (4, C) 是一个陈旧（stale） 的条目，因为 C 已经在第二次循环时通过路径 A->B->C 被更新为了更短的距离 2。因此，我们直接忽略这个顶点，不做任何处理。这种处理陈旧条目的能力是使用优先队列实现时的关键优化。

第六次循环：

  • 出队：弹出顶点 E（dist[E] = 5）。
  • 检查邻居：顶点 E 有一个邻居：D。
  • 松弛操作：
    • 对于邻居 D：dist[E] + w(E, D) = 5 + 2 = 7。7 > 3（当前 dist[D] 的值）不成立。因此不更新。
  • 当前状态：
    • dist: { A:0, B:1, C:2, D:3, E:5 }
    • 优先队列: 空

循环结束。最终，dist 中存储的就是从源点 A 到所有顶点的最短距离。

时间复杂度分析

Dijkstra算法的时间复杂度取决于所使用的数据结构：

  • 使用数组遍历查找最小值：每次需要 O(V) 的时间来找到未访问集合中的最小值顶点，总共需要循环 V 次，并对每条边进行一次松弛操作（O(E)）。总时间复杂度为 O(V² + E)。这在稠密图（边数 E 接近 V²）中表现良好。
  • 使用二叉堆（优先队列）：每次提取最小值（出队）是 O(log V)，每次减少键值（入队新距离，可能包含陈旧条目）也是 O(log V)。总操作次数最多为 O((V+E) log V)。因此，时间复杂度为 O((V+E) log V)。这在稀疏图（边数 E 远小于 V²）中更为高效。

关键点与限制

  1. 非负权重约束：这是Dijkstra算法的核心限制。如果图中存在负权边，算法可能无法得出正确结果。因为贪心策略假设一旦一个顶点被标记为“已访问”（加入集合S），其最短距离就不再改变。但负权边可能导致之前确定的“最短路径”实际上并非最短。对于含负权边的图，需要使用Bellman-Ford算法。
  2. 松弛操作：这是算法的核心步骤，通过它来不断优化到达每个顶点的距离估计值。
  3. 贪心选择性质：每次都选择当前看来最优的局部解（距离源点最近的未确定顶点），最终能得到全局最优解。

总结来说，Dijkstra算法通过巧妙的贪心策略和松弛操作，高效地解决了非负权图中的单源最短路径问题，是图论中最基础且重要的算法之一。

Dijkstra算法原理与实现 Dijkstra算法是解决 单源最短路径问题 的经典算法，由荷兰计算机科学家Edsger Dijkstra于1956年提出。它用于在 带非负权重的有向图或无向图 中，找到一个顶点（称为源点）到其他所有顶点的最短路径。 问题描述与核心思想 问题描述 ：给定一个图 G=(V, E)，其中 V 是顶点集合，E 是边集合。每条边 e = (u, v) 都有一个非负的权重 w(u, v)。给定一个源顶点 s，我们需要找出从 s 到图中 每一个其他顶点 v 的最短路径距离。 核心思想 ：Dijkstra算法采用了一种 贪心策略 。它维护一个集合 S，这个集合包含所有已经找到从源点 s 出发的最短路径的顶点。算法反复从尚未确定最短路径的顶点集合（V-S）中，选择一个 当前距离 s 最近的顶点 u，将其加入 S，然后对 u 的所有邻居顶点进行“松弛”操作。这个“最近”的判断是基于当前已知的、但不一定是最终的最短距离估计值。 可以通俗地理解为“多米诺骨牌”效应：一旦一个顶点的最短距离被最终确定，我们就可以放心地利用这个确定无疑的信息，去更新它所能影响到的周围邻居的距离估计。 算法步骤详解 我们用一个例子来逐步讲解。考虑以下有向图，源点为顶点 A。边上的数字代表权重。 步骤1：初始化 我们需要两个关键的数据结构： dist ：一个数组（或字典），用于记录从源点 s 到每个顶点 v 的 当前最短距离估计值 。 初始化： dist[s] = 0 （源点到自己的距离为0），对于其他所有顶点 v， dist[v] = ∞ （无穷大，表示尚未知）。 visited （或集合 S）：一个集合，用于记录哪些顶点的最短距离已经被 最终确定 。 初始化： visited 为空集。 另一种常见且高效的做法是使用一个 优先队列（最小堆） 来替代 visited 集合和遍历查找最小 dist 的过程。优先队列中存储 (当前距离估计值, 顶点) 对，并总是让距离最小的顶点出队。下面的讲解将采用这种更优的实现方式。 初始化结果 ： dist : { A:0, B:∞, C:∞, D:∞, E:∞ } 优先队列（最小堆）: [(0, A)] （初始时只有源点 A） 步骤2：循环处理，直到优先队列为空 第一次循环 ： 出队 ：从优先队列中弹出距离最小的顶点，即顶点 A（ dist[A] = 0 ）。 检查邻居 ：顶点 A 有两个邻居：B 和 C。 松弛操作 ：对于每个邻居顶点 v，检查如果通过当前顶点 u（即 A）到达 v，能否得到一条比当前已知路径更短的路径。即，判断 dist[u] + w(u, v) < dist[v] 是否成立。 对于邻居 B： dist[A] + w(A, B) = 0 + 1 = 1 。 1 < ∞ 成立。因此更新 dist[B] = 1 。同时，将 (1, B) 加入优先队列。 对于邻居 C： dist[A] + w(A, C) = 0 + 4 = 4 。 4 < ∞ 成立。因此更新 dist[C] = 4 。同时，将 (4, C) 加入优先队列。 此时，顶点 A 的最短距离被确定为 0。 当前状态 ： dist : { A:0, B:1, C:4, D:∞, E:∞ } 优先队列: [(1, B), (4, C)] 第二次循环 ： 出队 ：弹出距离最小的顶点 B（ dist[B] = 1 ）。 检查邻居 ：顶点 B 有两个邻居：D 和 C。 松弛操作 ： 对于邻居 D： dist[B] + w(B, D) = 1 + 2 = 3 。 3 < ∞ 成立。更新 dist[D] = 3 。将 (3, D) 入队。 对于邻居 C： dist[B] + w(B, C) = 1 + 1 = 2 。 2 < 4 （当前 dist[C] 的值）成立。这是一个关键步骤！我们发现了一条从 A 经 B 到 C 的更短路径（长度为2），优于之前直接 A->C 的路径（长度为4）。因此更新 dist[C] = 2 。注意，我们需要将 新的、更短的距离 (2, C) 加入优先队列。此时队列中会有两个关于 C 的条目 (2, C) 和 (4, C) ，但这没关系，当我们弹出 (4, C) 时，因为 C 已经被处理过（其 dist 已经变得更小），我们可以直接忽略这个陈旧的条目。 当前状态 ： dist : { A:0, B:1, C:2, D:3, E:∞ } 优先队列: [(2, C), (3, D), (4, C)] （注意队列中有两个 C） 第三次循环 ： 出队 ：弹出距离最小的顶点 C（ dist[C] = 2 ）。注意，即使队列中还有一个 (4, C) ，但我们先处理的是更小的 (2, C) 。 检查邻居 ：顶点 C 有一个邻居：E。 松弛操作 ： 对于邻居 E： dist[C] + w(C, E) = 2 + 3 = 5 。 5 < ∞ 成立。更新 dist[E] = 5 。将 (5, E) 入队。 当前状态 ： dist : { A:0, B:1, C:2, D:3, E:5 } 优先队列: [(3, D), (4, C), (5, E)] 第四次循环 ： 出队 ：弹出顶点 D（ dist[D] = 3 ）。 检查邻居 ：顶点 D 没有出边（邻居）。 松弛操作 ：无。 当前状态 ： dist : { A:0, B:1, C:2, D:3, E:5 } 优先队列: [(4, C), (5, E)] 第五次循环 ： 出队 ：弹出顶点 C（ dist[C] = 4 ）。但是，当我们检查当前记录时，发现 dist[C] 已经是 2（小于4）。这意味着我们弹出的这个 (4, C) 是一个 陈旧（stale） 的条目，因为 C 已经在第二次循环时通过路径 A->B->C 被更新为了更短的距离 2。因此，我们 直接忽略 这个顶点，不做任何处理。这种处理陈旧条目的能力是使用优先队列实现时的关键优化。 第六次循环 ： 出队 ：弹出顶点 E（ dist[E] = 5 ）。 检查邻居 ：顶点 E 有一个邻居：D。 松弛操作 ： 对于邻居 D： dist[E] + w(E, D) = 5 + 2 = 7 。 7 > 3 （当前 dist[D] 的值）不成立。因此不更新。 当前状态 ： dist : { A:0, B:1, C:2, D:3, E:5 } 优先队列: 空 循环结束 。最终， dist 中存储的就是从源点 A 到所有顶点的最短距离。 时间复杂度分析 Dijkstra算法的时间复杂度取决于所使用的数据结构： 使用数组遍历查找最小值 ：每次需要 O(V) 的时间来找到未访问集合中的最小值顶点，总共需要循环 V 次，并对每条边进行一次松弛操作（O(E)）。总时间复杂度为 O(V² + E) 。这在 稠密图 （边数 E 接近 V²）中表现良好。 使用二叉堆（优先队列） ：每次提取最小值（出队）是 O(log V)，每次减少键值（入队新距离，可能包含陈旧条目）也是 O(log V)。总操作次数最多为 O((V+E) log V)。因此，时间复杂度为 O((V+E) log V) 。这在 稀疏图 （边数 E 远小于 V²）中更为高效。 关键点与限制 非负权重约束 ：这是Dijkstra算法的 核心限制 。如果图中存在负权边，算法可能无法得出正确结果。因为贪心策略假设一旦一个顶点被标记为“已访问”（加入集合S），其最短距离就不再改变。但负权边可能导致之前确定的“最短路径”实际上并非最短。对于含负权边的图，需要使用Bellman-Ford算法。 松弛操作 ：这是算法的核心步骤，通过它来不断优化到达每个顶点的距离估计值。 贪心选择性质 ：每次都选择当前看来最优的局部解（距离源点最近的未确定顶点），最终能得到全局最优解。 总结来说，Dijkstra算法通过巧妙的贪心策略和松弛操作，高效地解决了非负权图中的单源最短路径问题，是图论中最基础且重要的算法之一。