图的单源最短路径：Dijkstra算法（堆优化版本）

字数 3536 2025-12-10 04:51:40

图的单源最短路径：Dijkstra算法（堆优化版本）

1. 题目描述

给定一个带权有向图（或无向图），图中每条边都有一个非负权重（距离/代价），以及一个源点（起点）。我们需要找出从源点到图中所有其他顶点的最短路径长度（即最短距离）。这个问题被称为单源最短路径问题（Single-Source Shortest Paths, SSSP）。Dijkstra算法是解决此问题的一种经典算法，特别适用于边权非负的图。这里我们将重点讲解其堆优化版本，这是面试和实践中最常用的高效实现。

2. 核心思想与前提条件

Dijkstra算法的核心思想是贪心策略：在每一步，从尚未确定最短距离的顶点集合中，选择一个当前距离源点最近的顶点，认为它的最短距离已经确定，然后利用它来更新其相邻顶点的距离估计。

重要前提：所有边的权重必须为非负数。如果图中存在负权边，Dijkstra算法可能无法得出正确结果，需要使用Bellman-Ford算法。

3. 基础概念准备

为了理解算法，我们先明确几个概念：

图表示：通常使用邻接表，更节省空间。对于每个顶点，存储一个列表，列表中包含其所有邻接点以及对应边的权重。例如，graph[u] 是一个列表，其中每个元素是一个元组 (v, w)，表示存在一条从 u 到 v 的边，权重为 w。
距离数组 dist：dist[v] 记录从源点 s 到顶点 v 的当前已知最短距离估计。初始时，dist[s] = 0，其他所有 dist[v] = ∞。
已确定集合与未确定集合：算法将顶点分为两类。一类是已确定最短距离的顶点，一旦顶点被加入这个集合，它的 dist 值就不会再被改变。另一类是未确定的顶点，它们的 dist 值是估计值，可能还会被更新。
优先队列（最小堆）：堆优化版本的核心数据结构。它存储的是 (当前距离估计, 顶点) 这样的对，并按照距离估计值进行排序（最小距离在堆顶）。这让我们能在 O(log V) 时间内快速取出当前距离源点最近的未确定顶点。

4. 算法步骤详解（堆优化版本）

步骤1：初始化

创建距离数组 dist，长度为顶点数 V。将所有 dist[v] 初始化为无穷大（如 float('inf')），除了源点 s：dist[s] = 0。
创建一个空的最小堆 min_heap（通常用Python的 heapq 库或C++的 priority_queue）。将源点及其距离推入堆中：(0, s)。
（可选）创建一个集合或布尔数组 visited 来标记顶点是否已确定最短距离。堆优化版本中，我们可以利用一个更简单的机制：当从堆中弹出一个顶点时，检查其距离是否已过时。

步骤2：主循环
当最小堆 min_heap 不为空时，循环执行以下操作：

弹出堆顶元素：弹出堆顶的 (current_dist, u)。这个 current_dist 是算法当前认为的从源点 s 到 u 的最短距离。
关键：有效性检查：如果 current_dist > dist[u]，说明这个记录是过时的。因为可能在此之前，我们已经通过其他路径找到了到达 u 的更短距离，并更新了 dist[u] 和堆。由于堆不支持直接修改元素，我们只能将新距离重新入堆，导致堆中存在旧记录。这个检查可以跳过这些无效的旧记录。如果无效，直接 continue。
标记已确定：此时，我们可以认为顶点 u 的最短距离已经最终确定。因为根据贪心选择性质，当前堆顶的距离是最小的，不可能有更短的路径了。
松弛操作（Relaxation）：遍历顶点 u 的所有邻居 v 以及对应的边权 w。
- 计算从源点 s 经过 u 到 v 的候选距离：new_dist = dist[u] + w。
- 如果 new_dist < dist[v]（即找到了更短的路径），则执行松弛：
  a. 更新距离数组：dist[v] = new_dist。
  b. 将新的 (new_dist, v) 对推入最小堆 min_heap 中。注意：我们并不删除堆中旧的 (dist_old, v) 记录，而是让其成为无效记录，留待步骤2中的有效性检查来处理。

步骤3：输出结果
当堆为空时，循环结束。此时 dist 数组中存储的就是从源点 s 到所有顶点的最短距离。对于无法到达的顶点，其 dist 值仍为无穷大。

5. 为什么需要堆优化？

朴素（未优化）的Dijkstra算法，在每次选择当前距离最近的顶点时，需要遍历所有未确定顶点来查找最小值，时间复杂度为 O(V)。由于需要做 V 次这样的选择，总复杂度为 O(V²)，适合稠密图。

堆优化版本利用优先队列（二叉最小堆）来管理未确定顶点的距离，使得：

弹出最小元素（Extract-Min）：O(log V)
减少键值（Decrease-Key，对应我们的入堆操作）：O(log V)（虽然我们入堆而不是直接修改，但总体分析后复杂度不变）

算法中，每个顶点最多被弹出一次，每次弹出会遍历其所有邻接边。总操作是：

每个顶点入堆、出堆各一次：O(V log V)
每条边最多引起一次入堆操作（当松弛成功时）：O(E log V)

因此，堆优化版本的总时间复杂度为 O((V+E) log V)，在稀疏图（E远小于V²）中效率远高于朴素版本。通常我们使用邻接表，所以该版本对稀疏图更优。

6. 举例说明

考虑一个简单无向图：
顶点：0, 1, 2, 3
边：(0,1,4), (0,2,2), (1,2,1), (1,3,5), (2,3,8)
源点：0

执行过程（简述）：

初始：dist = [0, inf, inf, inf], 堆 = [(0,0)]
弹出(0,0)：松弛边(0,1,4)->更新dist[1]=4，入堆(4,1)；松弛(0,2,2)->更新dist[2]=2，入堆(2,2)。
-> dist = [0, 4, 2, inf], 堆 = [(2,2), (4,1)]
弹出(2,2)：松弛边(2,1,1)->new_dist=2+1=3<4，更新dist[1]=3，入堆(3,1)；松弛(2,3,8)->更新dist[3]=10，入堆(10,3)。
-> dist = [0, 3, 2, 10], 堆 = [(3,1), (4,1), (10,3)] (注意堆中有两个关于顶点1的记录)
弹出(3,1)：检查 current_dist=3 等于 dist[1]=3，有效。松弛边(1,3,5)->new_dist=3+5=8<10，更新dist[3]=8，入堆(8,3)。
-> dist = [0, 3, 2, 8], 堆 = [(4,1), (8,3), (10,3)]
弹出(4,1)：检查 current_dist=4 > dist[1]=3，此为过时记录，跳过（continue）。
弹出(8,3)：有效。顶点3无未访问邻居（或都已确定），无需操作。
弹出(10,3)：过时记录，跳过。
堆空，结束。最终 dist = [0, 3, 2, 8]。

7. 关键要点与常见问题

负权边：Dijkstra算法不能处理带有负权边的图，因为其贪心选择性质基于“当前最短即全局最短”的前提，负权边可能破坏这个前提。
为什么需要有效性检查：因为同一个顶点可能因为被多次松弛而多次入堆。最早入堆的（较大的）距离记录会成为无效的“旧记录”。不检查会导致算法效率降低，甚至可能出错（如果继续用旧距离去松弛邻居）。
空间复杂度：主要为邻接表 O(V+E)，堆在最坏情况下可能存储 O(E) 个元素，故空间复杂度 O(V+E)。
获取路径：如果需要输出具体的最短路径，而不仅仅是距离，可以额外维护一个 prev（或 parent）数组，在松弛成功更新 dist[v] 时，记录 prev[v] = u。最后从终点回溯即可得到路径。
稠密图：当图非常稠密（E ≈ V²）时，朴素O(V²)的实现可能比O((V+E)log V)的堆优化更快，因为堆操作的常数因子较大。

通过以上步骤，你应该能理解Dijkstra算法（堆优化版本）如何高效地、逐步确定从单一源点到所有其他顶点的最短距离。

图的单源最短路径：Dijkstra算法（堆优化版本） 1. 题目描述给定一个带权有向图（或无向图），图中每条边都有一个非负权重（距离/代价），以及一个源点（起点）。我们需要找出从源点到图中所有其他顶点的最短路径长度（即最短距离）。这个问题被称为单源最短路径问题（Single-Source Shortest Paths, SSSP）。Dijkstra算法是解决此问题的一种经典算法，特别适用于边权非负的图。这里我们将重点讲解其堆优化版本，这是面试和实践中最常用的高效实现。 2. 核心思想与前提条件 Dijkstra算法的核心思想是贪心策略：在每一步，从尚未确定最短距离的顶点集合中，选择一个当前距离源点最近的顶点，认为它的最短距离已经确定，然后利用它来更新其相邻顶点的距离估计。重要前提：所有边的权重必须为非负数。如果图中存在负权边，Dijkstra算法可能无法得出正确结果，需要使用Bellman-Ford算法。 3. 基础概念准备为了理解算法，我们先明确几个概念：图表示：通常使用邻接表，更节省空间。对于每个顶点，存储一个列表，列表中包含其所有邻接点以及对应边的权重。例如， graph[u] 是一个列表，其中每个元素是一个元组 (v, w) ，表示存在一条从 u 到 v 的边，权重为 w 。距离数组 dist ： dist[v] 记录从源点 s 到顶点 v 的当前已知最短距离估计。初始时， dist[s] = 0 ，其他所有 dist[v] = ∞ 。已确定集合与未确定集合：算法将顶点分为两类。一类是已确定最短距离的顶点，一旦顶点被加入这个集合，它的 dist 值就不会再被改变。另一类是未确定的顶点，它们的 dist 值是估计值，可能还会被更新。优先队列（最小堆）：堆优化版本的核心数据结构。它存储的是 (当前距离估计, 顶点) 这样的对，并按照距离估计值进行排序（最小距离在堆顶）。这让我们能在 O(log V) 时间内快速取出当前距离源点最近的未确定顶点。 4. 算法步骤详解（堆优化版本）步骤1：初始化创建距离数组 dist ，长度为顶点数 V 。将所有 dist[v] 初始化为无穷大（如 float('inf') ），除了源点 s ： dist[s] = 0 。创建一个空的最小堆 min_heap （通常用Python的 heapq 库或C++的 priority_queue ）。将源点及其距离推入堆中： (0, s) 。（可选）创建一个集合或布尔数组 visited 来标记顶点是否已确定最短距离。堆优化版本中，我们可以利用一个更简单的机制：当从堆中弹出一个顶点时，检查其距离是否已过时。步骤2：主循环当最小堆 min_heap 不为空时，循环执行以下操作：弹出堆顶元素：弹出堆顶的 (current_dist, u) 。这个 current_dist 是算法当前认为的从源点 s 到 u 的最短距离。关键：有效性检查：如果 current_dist > dist[u] ，说明这个记录是过时的。因为可能在此之前，我们已经通过其他路径找到了到达 u 的更短距离，并更新了 dist[u] 和堆。由于堆不支持直接修改元素，我们只能将新距离重新入堆，导致堆中存在旧记录。这个检查可以跳过这些无效的旧记录。如果无效，直接 continue 。标记已确定：此时，我们可以认为顶点 u 的最短距离已经最终确定。因为根据贪心选择性质，当前堆顶的距离是最小的，不可能有更短的路径了。松弛操作（Relaxation）：遍历顶点 u 的所有邻居 v 以及对应的边权 w 。计算从源点 s 经过 u 到 v 的候选距离： new_dist = dist[u] + w 。如果 new_dist < dist[v] （即找到了更短的路径），则执行松弛： a. 更新距离数组： dist[v] = new_dist 。 b. 将新的 (new_dist, v) 对推入最小堆 min_heap 中。注意：我们并不删除堆中旧的 (dist_old, v) 记录，而是让其成为无效记录，留待步骤2中的有效性检查来处理。步骤3：输出结果当堆为空时，循环结束。此时 dist 数组中存储的就是从源点 s 到所有顶点的最短距离。对于无法到达的顶点，其 dist 值仍为无穷大。 5. 为什么需要堆优化？朴素（未优化）的Dijkstra算法，在每次选择当前距离最近的顶点时，需要遍历所有未确定顶点来查找最小值，时间复杂度为 O(V)。由于需要做 V 次这样的选择，总复杂度为 O(V²) ，适合稠密图。堆优化版本利用优先队列（二叉最小堆）来管理未确定顶点的距离，使得：弹出最小元素（Extract-Min）：O(log V) 减少键值（Decrease-Key，对应我们的入堆操作）：O(log V)（虽然我们入堆而不是直接修改，但总体分析后复杂度不变）算法中，每个顶点最多被弹出一次，每次弹出会遍历其所有邻接边。总操作是：每个顶点入堆、出堆各一次：O(V log V) 每条边最多引起一次入堆操作（当松弛成功时）：O(E log V) 因此，堆优化版本的总时间复杂度为 O((V+E) log V) ，在稀疏图（E远小于V²）中效率远高于朴素版本。通常我们使用邻接表，所以该版本对稀疏图更优。 6. 举例说明考虑一个简单无向图：顶点：0, 1, 2, 3 边：(0,1,4), (0,2,2), (1,2,1), (1,3,5), (2,3,8) 源点：0 执行过程（简述）：初始： dist = [0, inf, inf, inf] , 堆 = [(0,0)] 弹出(0,0)：松弛边(0,1,4)->更新 dist[1]=4 ，入堆(4,1)；松弛(0,2,2)->更新 dist[2]=2 ，入堆(2,2)。 -> dist = [0, 4, 2, inf] , 堆 = [(2,2), (4,1)] 弹出(2,2)：松弛边(2,1,1)-> new_dist=2+1=3 <4，更新 dist[1]=3 ，入堆(3,1)；松弛(2,3,8)->更新 dist[3]=10 ，入堆(10,3)。 -> dist = [0, 3, 2, 10] , 堆 = [(3,1), (4,1), (10,3)] (注意堆中有两个关于顶点1的记录) 弹出(3,1)：检查 current_dist=3 等于 dist[1]=3 ，有效。松弛边(1,3,5)-> new_dist=3+5=8 <10，更新 dist[3]=8 ，入堆(8,3)。 -> dist = [0, 3, 2, 8] , 堆 = [(4,1), (8,3), (10,3)] 弹出(4,1)：检查 current_dist=4 > dist[1]=3 ，此为过时记录，跳过（ continue ）。弹出(8,3)：有效。顶点3无未访问邻居（或都已确定），无需操作。弹出(10,3)：过时记录，跳过。堆空，结束。最终 dist = [0, 3, 2, 8] 。 7. 关键要点与常见问题负权边：Dijkstra算法不能处理带有负权边的图，因为其贪心选择性质基于“当前最短即全局最短”的前提，负权边可能破坏这个前提。为什么需要有效性检查：因为同一个顶点可能因为被多次松弛而多次入堆。最早入堆的（较大的）距离记录会成为无效的“旧记录”。不检查会导致算法效率降低，甚至可能出错（如果继续用旧距离去松弛邻居）。空间复杂度：主要为邻接表 O(V+E)，堆在最坏情况下可能存储 O(E) 个元素，故空间复杂度 O(V+E)。获取路径：如果需要输出具体的最短路径，而不仅仅是距离，可以额外维护一个 prev （或 parent ）数组，在松弛成功更新 dist[v] 时，记录 prev[v] = u 。最后从终点回溯即可得到路径。稠密图：当图非常稠密（E ≈ V²）时，朴素O(V²)的实现可能比O((V+E)log V)的堆优化更快，因为堆操作的常数因子较大。通过以上步骤，你应该能理解Dijkstra算法（堆优化版本）如何高效地、逐步确定从单一源点到所有其他顶点的最短距离。