Skip to Content

Dijkstra 算法详解

1. 算法概述

  • 目标：给定一个带权图和一个特定的起始顶点（源点 s），Dijkstra 算法用于找出从源点 s 到图中所有其他顶点的最短路径。
  • 核心思想：贪心算法 (Greedy Algorithm)。
  • 别名：单源最短路径算法 (Single-Source Shortest Path, SSSP)。
  • 关键限制：图中所有边的权重必须为非负数（即不能有负权边）。

2. 核心思想：贪心策略

Dijkstra 算法的贪心思想可以形象地比喻为“火势蔓延”或“涟漪扩散”。

  1. 初始化：把所有顶点分为两组：

    • 已确定最短路径的顶点集合 S ( initially, only contains the source s )。
    • 未确定最短路径的顶点集合 U ( initially, contains all other vertices )。

  2. 贪心选择：在每一步，算法都会从 U 集合中，选择一个距离源点 s 最近的顶点 u。这个选择是“贪心”的，因为它认为当前看起来最近的，就是最终最近的。

  3. 加入与松弛：将选出的顶点 u 从 U 移动到 S。然后，以 u 为“中转站”，检查并更新 u 的所有邻居 v 的距离。这个更新过程称为松弛 (Relaxation)。

    • 松弛操作：如果“从源点 s 到 u 的距离”加上“从 u到 v 的距离”比“当前记录的从 s 到 v 的距离”更短，那么就更新 s 到 v 的距离。
    • 即：if (dist[u] + weight(u, v) < dist[v]) { dist[v] = dist[u] + weight(u, v); }

  4. 重复：重复步骤 2 和 3，直到 U 集合为空，即所有顶点的最短路径都已确定。

3. 算法步骤与所需数据结构

  • dist[] 数组：一个大小为 V (顶点数) 的数组，dist[i] 存储从源点 s 到顶点 i 的当前已知的最短路径长度。
  • visited[] 布尔数组：记录哪些顶点已经属于集合 S (其最短路径已确定)。
  • 优先队列 (Min-Priority Queue)：这是实现 Dijkstra 算法最高效的方式。它被用来存储 U 集合中的顶点，并能以 O(log V) 的时间复杂度快速找出 dist 值最小的顶点。

详细步骤 (使用优先队列)：

  1. 初始化：

    • 创建一个 dist 数组，将 dist[s] 初始化为 0，所有其他 dist[i] 初始化为 ∞。
    • 创建一个优先队列 pq，将源点 s 和其距离 0（即 <0, s>）放入队列。

  2. 主循环：当优先队列 pq 不为空时，循环执行：

    • a. 从 pq 中提取具有最小距离的顶点 u。
    • b. 如果 u 已经被访问过 (在某些实现中可能出现冗余项)，则跳过此次循环。否则，将其标记为已访问。
    • c. 遍历 u 的所有邻居 v：
      • 执行松弛操作：计算新路径 dist[u] + weight(u, v)。
      • 如果新路径更短 (dist[u] + weight(u, v) < dist[v])，则更新 dist[v] 的值为新路径长度，并将新的 <dist[v], v> 放入优先队列 pq。

  3. 完成：当循环结束时，dist 数组中就存储了从源点 s 到所有其他顶点的最短路径长度。

4. 实例推演

让我们用和 Floyd 例子类似的图，但去掉负权边，并指定源点为 0。

Step 1: 初始化

  • dist = {0, INF, INF, INF}
  • visited = {F, F, F, F}
  • pq = { <0, 0> }

Step 2: 迭代

Iteration 1:

  • 从 pq 提取最小元素：<0, 0>。顶点 u=0。
  • 标记 visited[0] = T。
  • 松弛 0 的邻居：
    • 邻居 1: dist[0] + w(0,1) = 0 + 3 = 3 < dist[1] (INF)。更新 dist[1]=3。将 <3, 1> 入队。
    • 邻居 3: dist[0] + w(0,3) = 0 + 5 = 5 < dist[3] (INF)。更新 dist[3]=5。将 <5, 3> 入队。
  • 当前状态: dist={0, 3, INF, 5}, pq={<3, 1>, <5, 3>}

Iteration 2:

  • 从 pq 提取最小元素：<3, 1>。顶点 u=1。
  • 标记 visited[1] = T。
  • 松弛 1 的邻居：
    • 邻居 0: 已访问，跳过。
    • 邻居 3: dist[1] + w(1,3) = 3 + 4 = 7。dist[3] 当前是5。7 不小于 5，不更新。
  • 当前状态: dist={0, 3, INF, 5}, pq={<5, 3>}

Iteration 3:

  • 从 pq 提取最小元素：<5, 3>。顶点 u=3。
  • 标记 visited[3] = T。
  • 松弛 3 的邻居：
    • 邻居 2: dist[3] + w(3,2) = 5 + 2 = 7 < dist[2] (INF)。更新 dist[2]=7。将 <7, 2> 入队。
  • 当前状态: dist={0, 3, 7, 5}, pq={<7, 2>}

Iteration 4:

  • 从 pq 提取最小元素：<7, 2>。顶点 u=2。
  • 标记 visited[2] = T。
  • 松弛 2 的邻居：
    • 邻居 1: 已访问，跳过。
  • 当前状态: dist={0, 3, 7, 5}, pq={}

Step 3: 完成 pq 为空，算法结束。最终 dist 数组为 {0, 3, 7, 5}，表示从源点0到各点的最短路径长度。

5. 为什么不能处理负权边？

Dijkstra 的贪心策略基于一个前提：一旦一个顶点 u 被选为当前最近的顶点并加入集合 S，那么 dist[u] 的值就已经最终确定了，不可能再有更短的路径。

但如果存在负权边，这个前提就会被打破。一个当前看似较远的路径，未来可能因为经过一条权值很小的负权边而变得更短。

反例：s -> A -> B。w(s,A)=5, w(s,B)=10, w(A,B)=-6。

  1. Dijkstra 先确定 s 到 A 的最短路是5，将A加入S。
  2. 然后它会认为 s 到 B 的最短路是10。
  3. 但实际上，s -> A -> B 这条路的长度是 5 + (-6) = -1，比10更短。但因为A已经加入S被“最终确定”，Dijkstra 算法不会再通过A来更新其他点的路径，从而导致错误。

Dijkstra vs. Floyd 算法对比

这是一个非常经典的面试和考试考点。下面通过一个表格来清晰地对比它们：

特性Dijkstra 算法Floyd-Warshall 算法
解决问题单源最短路径 (SSSP)
从一个指定的源点到所有其他点的最短路径。		所有节点对最短路径 (APSP)
图中任意两点之间的最短路径。
核心思想贪心算法 (Greedy)
每步都选择当前未访问顶点中离源点最近的一个。		动态规划 (Dynamic Programming)
通过不断增加中转点来逐步逼近最优解。
负权边处理不能处理
贪心选择的前提是边的权重非负。		可以处理
但不能处理负权环路。
数据结构邻接表（稀疏图）或邻接矩阵（稠密图）。
通常配合优先队列来优化。		必须使用邻接矩阵来存储距离。
时间复杂度- 使用优先队列: O(E log V)
- 使用数组暴力查找: O(V^2)		O(V^3)
空间复杂度O(V + E) (邻接表)O(V^2) (邻接矩阵)
适用场景- 求单点到其他所有点的最短路。
- 稀疏图 (E 远小于 V^2) 效率更高。		- 求所有点对之间的最短路。
- 稠密图或顶点数较少时适用。
- 图中存在负权边时。
运行方式从源点开始，像波浪一样向外扩展。三重循环，系统性地尝试所有可能的中转点。

总结与选择

  • 问题是“从A点出发到其他所有点的最短路”吗？

    • 是 -> 检查有无负权边。
      • 无负权边 -> Dijkstra 是最佳选择，因为它更快。
      • 有负权边 -> 不能用 Dijkstra，应使用 Bellman-Ford 或 SPFA 算法。

  • 问题是“求任意两点之间的最短路”吗？

    • 是 -> 检查有无负权边。
      • 无负权边 -> 你有两种选择：
        1. 运行 V 次 Dijkstra 算法（每个点作一次源点）。总复杂度为 V * O(E log V)。在稀疏图上，这可能比 O(V^3) 更优。
        2. 直接使用 Floyd 算法。在稠密图上，或者当代码简洁性更重要时，Floyd 更方便。
      • 有负权边 (但无负权环) -> 只能使用 Floyd 算法。
Last updated on
Map