贪心算法 - 单源最短路径 - Dijkstra 算法的贪心策略

贪心算法 - 单源最短路径 - Dijkstra 算法的贪心策略

一、引言

在现实生活中，我们常常会遇到寻找最短路径的问题。比如，在地图导航中，我们希望找到从一个地点到另一个地点的最短路线；在网络通信中，需要找到数据包传输的最短路径等。Dijkstra 算法就是解决这类单源最短路径问题的经典算法，它基于贪心策略，能高效地找到从一个特定源点到图中其他所有顶点的最短路径。

二、贪心算法概述

贪心算法是一种在每一步选择中都采取当前状态下最优（即最有利）的选择，从而希望导致结果是全局最优的算法。它并不从整体最优上加以考虑，所做的仅是在某种意义上的局部最优选择。虽然贪心算法不能保证总是得到全局最优解，但在许多问题中，它可以得到最优解，Dijkstra 算法就是其中之一。

三、单源最短路径问题

单源最短路径问题是指在一个带权有向图 $G=(V, E)$ 中，给定一个源顶点 $s \in V$，找出从 $s$ 到图中所有其他顶点的最短路径。这里的“最短路径”通常指路径上所有边的权值之和最小。

四、Dijkstra 算法的贪心策略

（一）算法基本思想

Dijkstra 算法的核心思想是基于贪心策略，逐步扩展已确定最短路径的顶点集合。算法维护两个集合：一个集合 $S$ 包含已经确定最短路径的顶点，另一个集合 $V - S$ 包含尚未确定最短路径的顶点。在每一步，算法从 $V - S$ 中选择一个距离源点 $s$ 最近的顶点 $u$，将其加入集合 $S$ 中，并更新与 $u$ 相邻的顶点的最短路径估计值。

（二）具体步骤

1. 初始化：
   • 设源点为 $s$，将集合 $S$ 初始化为只包含源点 $s$，即 $S = {s}$。
   • 对于图中的每个顶点 $v$，初始化其距离源点的最短路径估计值 $d[v]$。若 $v = s$，则 $d[s] = 0$；否则，$d[v] = +\infty$。
   • 同时，初始化每个顶点的前驱顶点 $prev[v] = NULL$。
2. 迭代过程：
   • 当 $S \neq V$ 时，执行以下操作：
     • 从 $V - S$ 中选择一个距离源点 $s$ 最近的顶点 $u$，即 $d[u]$ 最小的顶点。
     • 将顶点 $u$ 加入集合 $S$ 中。
     • 对于与 $u$ 相邻的每个顶点 $v$，如果通过 $u$ 到达 $v$ 的路径长度小于当前 $v$ 的最短路径估计值 $d[v]$，则更新 $d[v]$ 和 $prev[v]$：
       • $d[v] = d[u] + w(u, v)$，其中 $w(u, v)$ 是边 $(u, v)$ 的权值。
       • $prev[v] = u$。
3. 结束：当 $S = V$ 时，算法结束，此时 $d[v]$ 即为从源点 $s$ 到顶点 $v$ 的最短路径长度，通过 $prev$ 数组可以回溯得到最短路径。

（三）贪心策略分析

Dijkstra 算法的贪心策略体现在每次都选择距离源点最近的顶点加入集合 $S$。这种选择基于一个重要的性质：一旦一个顶点被加入集合 $S$，其最短路径就已经确定，不会再被更新。这是因为在后续的迭代中，通过其他顶点到达该顶点的路径长度必然不会小于当前已经确定的最短路径长度。

五、实例分析

假设有一个带权有向图，其顶点集合 $V = {A, B, C, D, E}$，边集合 $E$ 及其权值如下表所示：

我们以顶点 $A$ 为源点，使用 Dijkstra 算法计算从 $A$ 到其他顶点的最短路径。

（一）初始化

• $S = {A}$
• $d[A] = 0$，$d[B] = +\infty$，$d[C] = +\infty$，$d[D] = +\infty$，$d[E] = +\infty$
• $prev[A] = NULL$，$prev[B] = NULL$，$prev[C] = NULL$，$prev[D] = NULL$，$prev[E] = NULL$

（二）第一次迭代

• 从 $V - S = {B, C, D, E}$ 中选择距离源点 $A$ 最近的顶点，由于 $d[A] = 0$，与 $A$ 相邻的顶点 $B$ 和 $C$ 的距离更新为：
  • $d[B] = d[A] + w(A, B) = 0 + 4 = 4$，$prev[B] = A$
  • $d[C] = d[A] + w(A, C) = 0 + 2 = 2$，$prev[C] = A$
• 选择 $d$ 值最小的顶点 $C$ 加入集合 $S$，此时 $S = {A, C}$

（三）第二次迭代

• 与 $C$ 相邻的顶点有 $B$、$D$ 和 $E$。
  • 对于顶点 $B$，$d[B] = 4$，$d[C] + w(C, B) = 2 + 5 = 7 > 4$，不更新 $d[B]$ 和 $prev[B]$。
  • 对于顶点 $D$，$d[D] = +\infty$，$d[C] + w(C, D) = 2 + 3 = 5$，更新 $d[D] = 5$，$prev[D] = C$。
  • 对于顶点 $E$，$d[E] = +\infty$，$d[C] + w(C, E) = 2 + 8 = 10$，更新 $d[E] = 10$，$prev[E] = C$。
• 从 $V - S = {B, D, E}$ 中选择 $d$ 值最小的顶点 $B$ 加入集合 $S$，此时 $S = {A, C, B}$

（四）第三次迭代

• 与 $B$ 相邻的顶点有 $D$。
  • 对于顶点 $D$，$d[D] = 5$，$d[B] + w(B, D) = 4 + 10 = 14 > 5$，不更新 $d[D]$ 和 $prev[D]$。
• 从 $V - S = {D, E}$ 中选择 $d$ 值最小的顶点 $D$ 加入集合 $S$，此时 $S = {A, C, B, D}$

（五）第四次迭代

• 与 $D$ 相邻的顶点有 $E$。
  • 对于顶点 $E$，$d[E] = 10$，$d[D] + w(D, E) = 5 + 7 = 12 > 10$，不更新 $d[E]$ 和 $prev[E]$。
• 选择顶点 $E$ 加入集合 $S$，此时 $S = {A, C, B, D, E}$，算法结束。

最终得到从源点 $A$ 到其他顶点的最短路径长度分别为：$d[B] = 4$，$d[C] = 2$，$d[D] = 5$，$d[E] = 10$。

六、复杂度分析

• 时间复杂度：Dijkstra 算法的时间复杂度取决于所使用的数据结构。如果使用朴素的数组来存储顶点的距离信息，每次选择距离源点最近的顶点需要遍历所有未确定最短路径的顶点，时间复杂度为 $O(V^2)$，其中 $V$ 是图的顶点数。如果使用优先队列（如二叉堆）来优化选择过程，时间复杂度可以降低到 $O((V + E) \log V)$，其中 $E$ 是图的边数。
• 空间复杂度：主要用于存储顶点的距离信息和前驱顶点信息，空间复杂度为 $O(V)$。

七、总结

Dijkstra 算法通过贪心策略，每次选择距离源点最近的顶点加入已确定最短路径的集合，逐步扩展得到从源点到图中其他所有顶点的最短路径。该算法在处理单源最短路径问题时非常高效，但要求图中所有边的权值非负。通过合理选择数据结构，可以进一步优化算法的时间复杂度。在实际应用中，Dijkstra 算法广泛用于地图导航、网络路由等领域，为解决最短路径问题提供了一种有效的方法。

通过上述内容，我们可以清晰地看到 Dijkstra 算法的贪心策略的具体实现和应用，以及它在解决单源最短路径问题中的优势和局限性。在实际使用时，我们可以根据具体问题的特点选择合适的算法和数据结构，以达到最佳的效果。