图的最短路径算法
字数 2978 2025-11-07 12:33:56

图的最短路径算法

图的最短路径问题是图论中的一个经典问题，旨在寻找图中两个节点之间路径权重之和最小的路径。其中，Dijkstra算法是解决非负权重图单源最短路径问题最著名的算法。

1. 问题描述与核心思想

假设我们有一个带权有向图（或无向图），其中每条边都有一个非负的权重（可以理解为距离、成本或时间）。给定一个源节点（起点），Dijkstra算法的目标是找出从源节点到图中所有其他节点的最短路径及其长度。

核心思想：采用贪心策略。它维护一个集合，其中包含已经找到最短路径的节点。算法逐步扩展这个集合，每次从尚未确定最短路径的节点中，选择一个距离源节点最近的节点加入集合，并更新其邻居节点的距离估计。

2. 算法所需的数据结构

为了高效实现算法，我们需要以下数据结构：

  • dist: 一个数组（或字典），用于记录从源节点到每个节点的当前已知最短距离。初始时，源节点的距离设为0，其他所有节点的距离设为无穷大（∞）。
  • visited (或 finalized_set): 一个集合（或布尔数组），用于标记哪些节点的最短距离已经被最终确定。
  • priority_queue: 一个优先队列（最小堆），用于高效地选出当前距离源节点最近且未被访问过的节点。队列中的元素通常是(distance, node)对。

3. 算法步骤分解

让我们一步步拆解Dijkstra算法的工作流程：

步骤零：初始化

  • 创建dist字典/数组。设置dist[source] = 0，对于图中所有其他节点v，设置dist[v] = ∞。
  • 创建visited集合，初始为空。
  • 创建优先队列pq，并将源节点(0, source)加入队列。

步骤一：选择当前最近节点

  • 从优先队列pq中弹出当前距离最小的节点，记为current_node（第一次弹出的一定是源节点）。
  • 检查：如果current_node已经在visited集合中，则跳过它（这意味着它有更短的距离已经被处理过了，当前弹出的是个旧的、无效的记录）。否则，继续下一步。
  • 将current_node标记为已访问（加入visited集合）。此时，dist[current_node]的值就是从源节点到current_node的最终最短距离。这个选择是贪心且正确的，因为在非负权图中，不可能通过其他未访问节点找到一条更短的路径到达current_node。

步骤二：松弛操作

  • 遍历current_node的所有未被访问的邻居节点neighbor。
  • 计算一条经由current_node到达neighbor的潜在新路径长度：new_distance = dist[current_node] + weight(current_node, neighbor)。
  • 比较：如果计算出的new_distance小于当前记录的dist[neighbor]，则说明我们找到了一条更短的路径。
    • 更新dist[neighbor]为new_distance。
    • 将(new_distance, neighbor)这个新的距离估计加入优先队列pq。注意，队列中可能已经存在neighbor的旧距离记录，我们不需要删除它，只需加入新的（更小的）记录即可。在步骤一的检查中，旧的记录会被跳过。

步骤三：循环

  • 重复步骤一和步骤二，直到优先队列pq为空，或者我们已经访问了所有需要访问的节点（有时我们只关心到特定目标节点的最短路径，找到后可以提前终止）。

4. 一个详细的例子

考虑下图，我们以节点A为源点，求它到其他节点的最短路径。边上的数字代表距离。

    (B)
  1/   \4
 (A)   (D)
  5\   /1
    (C)
  • A到B权重1，A到C权重5，B到D权重4，C到D权重1。

初始化:
dist: A=0, B=∞, C=∞, D=∞
visited: {}
pq: [(0, A)]

第一轮循环:

  • 弹出pq中最小距离节点(A, 0)。A不在visited中，将其加入visited。visited = {A}。
  • 松弛A的邻居：B和C。
    • 对于B: new_dist = 0 + 1 = 1。1 < ∞，更新dist[B] = 1，将(B, 1)加入pq。
    • 对于C: new_dist = 0 + 5 = 5。5 < ∞，更新dist[C] = 5，将(C, 5)加入pq。
  • 此时dist: A=0, B=1, C=5, D=∞。pq: [(1, B), (5, C)]

第二轮循环:

  • 弹出pq中最小距离节点(B, 1)。B不在visited中，将其加入visited。visited = {A, B}。
  • 松弛B的邻居：D。
    • 对于D: new_dist = 1 + 4 = 5。5 < ∞，更新dist[D] = 5，将(D, 5)加入pq。
  • 此时dist: A=0, B=1, C=5, D=5。pq: [(5, C), (5, D)]

第三轮循环:

  • 弹出pq中最小距离节点(C, 5)。C不在visited中，将其加入visited。visited = {A, B, C}。
  • 松弛C的邻居：D。
    • 对于D: new_dist = 5 + 1 = 6。6 > 当前dist[D]=5，所以不更新。
  • 此时dist不变。pq: [(5, D)]

第四轮循环:

  • 弹出pq中最小距离节点(D, 5)。D不在visited中，将其加入visited。visited = {A, B, C, D}。
  • D没有未访问的邻居（所有节点都已访问），无需松弛。
  • 此时pq为空。

算法结束。最终最短距离为：A到A:0, A到B:1, A到C:5, A到D:5。
路径A->B->D和A->C->D的距离都是5，但算法找到的是第一条。

5. 时间复杂度分析

  • 每个节点被加入和弹出优先队列一次，操作次数为O(V)。
  • 每条边会被遍历一次用于松弛操作，次数为O(E)。
  • 优先队列（最小堆）的插入和删除操作时间复杂度为O(log V)。
  • 因此，使用优先队列的Dijkstra算法总时间复杂度为O((V + E) log V)。如果图是连通图，E至少为V-1，可以简化为O(E log V)。

6. 关键点与注意事项

  • 非负权重约束：这是Dijkstra算法正确性的基石。如果存在负权边，贪心选择“当前最近节点”的策略可能失效，因为后续可能通过负权边缩短路径。对于含负权边的图，需要使用Bellman-Ford算法。
  • 路径重建：上述过程只计算了最短距离。要记录具体路径，需要维护一个prev（或parent)数组，在每次成功松弛更新dist时，记录prev[neighbor] = current_node。最后从目标节点反向追踪prev数组即可得到路径。
  • 优先队列的优化：使用斐波那契堆可以实现更优的理论时间复杂度O(E + V log V)，但在实际应用中，二叉堆（即通常的优先队列）因其常数因子小而被广泛使用。
图的最短路径算法 图的最短路径问题是图论中的一个经典问题，旨在寻找图中两个节点之间路径权重之和最小的路径。其中，Dijkstra算法是解决非负权重图单源最短路径问题最著名的算法。 1. 问题描述与核心思想 假设我们有一个带权有向图（或无向图），其中每条边都有一个非负的权重（可以理解为距离、成本或时间）。给定一个源节点（起点），Dijkstra算法的目标是找出从源节点到图中所有其他节点的最短路径及其长度。 核心思想：采用贪心策略。它维护一个集合，其中包含已经找到最短路径的节点。算法逐步扩展这个集合，每次从尚未确定最短路径的节点中，选择一个距离源节点最近的节点加入集合，并更新其邻居节点的距离估计。 2. 算法所需的数据结构 为了高效实现算法，我们需要以下数据结构： dist : 一个数组（或字典），用于记录从源节点到每个节点的当前已知最短距离。初始时，源节点的距离设为0，其他所有节点的距离设为无穷大（∞）。 visited (或 finalized_set ): 一个集合（或布尔数组），用于标记哪些节点的最短距离已经被最终确定。 priority_queue : 一个优先队列（最小堆），用于高效地选出当前距离源节点最近且未被访问过的节点。队列中的元素通常是 (distance, node) 对。 3. 算法步骤分解 让我们一步步拆解Dijkstra算法的工作流程： 步骤零：初始化 创建 dist 字典/数组。设置 dist[source] = 0 ，对于图中所有其他节点 v ，设置 dist[v] = ∞ 。 创建 visited 集合，初始为空。 创建优先队列 pq ，并将源节点 (0, source) 加入队列。 步骤一：选择当前最近节点 从优先队列 pq 中弹出当前距离最小的节点，记为 current_node （第一次弹出的一定是源节点）。 检查 ：如果 current_node 已经在 visited 集合中，则跳过它（这意味着它有更短的距离已经被处理过了，当前弹出的是个旧的、无效的记录）。否则，继续下一步。 将 current_node 标记为已访问（加入 visited 集合）。 此时， dist[current_node] 的值就是从源节点到 current_node 的最终最短距离 。这个选择是贪心且正确的，因为在非负权图中，不可能通过其他未访问节点找到一条更短的路径到达 current_node 。 步骤二：松弛操作 遍历 current_node 的所有 未被访问 的邻居节点 neighbor 。 计算一条经由 current_node 到达 neighbor 的潜在新路径长度： new_distance = dist[current_node] + weight(current_node, neighbor) 。 比较 ：如果计算出的 new_distance 小于当前记录的 dist[neighbor] ，则说明我们找到了一条更短的路径。 更新 dist[neighbor] 为 new_distance 。 将 (new_distance, neighbor) 这个新的距离估计加入优先队列 pq 。注意，队列中可能已经存在 neighbor 的旧距离记录，我们不需要删除它，只需加入新的（更小的）记录即可。在步骤一的检查中，旧的记录会被跳过。 步骤三：循环 重复 步骤一 和 步骤二 ，直到优先队列 pq 为空，或者我们已经访问了所有需要访问的节点（有时我们只关心到特定目标节点的最短路径，找到后可以提前终止）。 4. 一个详细的例子 考虑下图，我们以节点A为源点，求它到其他节点的最短路径。边上的数字代表距离。 A到B权重1，A到C权重5，B到D权重4，C到D权重1。 初始化 : dist : A=0, B=∞, C=∞, D=∞ visited : {} pq : [ (0, A) ] 第一轮循环 : 弹出 pq 中最小距离节点(A, 0)。A不在 visited 中，将其加入 visited 。 visited = {A}。 松弛A的邻居：B和C。 对于B: new_dist = 0 + 1 = 1 。1 < ∞，更新 dist[B] = 1 ，将(B, 1)加入 pq 。 对于C: new_dist = 0 + 5 = 5 。5 < ∞，更新 dist[C] = 5 ，将(C, 5)加入 pq 。 此时 dist : A=0, B=1, C=5, D=∞。 pq : [ (1, B), (5, C) ] 第二轮循环 : 弹出 pq 中最小距离节点(B, 1)。B不在 visited 中，将其加入 visited 。 visited = {A, B}。 松弛B的邻居：D。 对于D: new_dist = 1 + 4 = 5 。5 < ∞，更新 dist[D] = 5 ，将(D, 5)加入 pq 。 此时 dist : A=0, B=1, C=5, D=5。 pq : [ (5, C), (5, D) ] 第三轮循环 : 弹出 pq 中最小距离节点(C, 5)。C不在 visited 中，将其加入 visited 。 visited = {A, B, C}。 松弛C的邻居：D。 对于D: new_dist = 5 + 1 = 6 。6 > 当前 dist[D]=5 ，所以 不更新 。 此时 dist 不变。 pq : [ (5, D) ] 第四轮循环 : 弹出 pq 中最小距离节点(D, 5)。D不在 visited 中，将其加入 visited 。 visited = {A, B, C, D}。 D没有未访问的邻居（所有节点都已访问），无需松弛。 此时 pq 为空。 算法结束 。最终最短距离为：A到A:0, A到B:1, A到C:5, A到D:5。 路径A->B->D和A->C->D的距离都是5，但算法找到的是第一条。 5. 时间复杂度分析 每个节点被加入和弹出优先队列一次，操作次数为O(V)。 每条边会被遍历一次用于松弛操作，次数为O(E)。 优先队列（最小堆）的插入和删除操作时间复杂度为O(log V)。 因此，使用优先队列的Dijkstra算法总时间复杂度为 O((V + E) log V) 。如果图是连通图，E至少为V-1，可以简化为 O(E log V) 。 6. 关键点与注意事项 非负权重约束 ：这是Dijkstra算法正确性的基石。如果存在负权边，贪心选择“当前最近节点”的策略可能失效，因为后续可能通过负权边缩短路径。对于含负权边的图，需要使用Bellman-Ford算法。 路径重建 ：上述过程只计算了最短距离。要记录具体路径，需要维护一个 prev （或 parent )数组，在每次成功松弛更新 dist 时，记录 prev[neighbor] = current_node 。最后从目标节点反向追踪 prev 数组即可得到路径。 优先队列的优化 ：使用斐波那契堆可以实现更优的理论时间复杂度O(E + V log V)，但在实际应用中，二叉堆（即通常的优先队列）因其常数因子小而被广泛使用。