有向无环图（DAG）中的单源最短路径问题（拓扑排序解法）

字数 3895 2025-12-11 11:11:06

有向无环图（DAG）中的单源最短路径问题（拓扑排序解法）

我将为你讲解“有向无环图（DAG）中的单源最短路径问题”及其基于拓扑排序的解法。这个问题是图论中一个重要的基础算法，它利用DAG的特性，提供了比通用算法更高效的解决方案。

问题描述

给定一个有向无环图（DAG），图中每条边都有一个权重（可以是正数、负数或零）。同时指定一个源点 s。我们的目标是找出从源点 s 到图中所有其他顶点的最短路径距离。

关键特点：

图是有向的，且无环。这意味着图中不存在从一个顶点出发最终又能回到该顶点的有向路径。
边的权重可以是负数。这与Dijkstra算法（不能处理负权边）形成对比。
由于图中无环，也就不可能存在负权环，因此最短路径总是良定义的，不会出现“无穷小”的情况。

目标输出：
一个数组 dist[]，其中 dist[v] 表示从源点 s 到顶点 v 的最短路径距离。如果从 s 无法到达 v，则 dist[v] = ∞。

为什么这个问题特殊？

在通用有向图中，解决单源最短路径问题通常使用：

Bellman-Ford算法：时间复杂度 O(VE)，可处理负权边，并能检测负权环。
SPFA算法：Bellman-Ford的队列优化，最坏复杂度仍是O(VE)。

然而，由于DAG具有线性顺序（拓扑序）这一优良性质，我们可以先对图进行拓扑排序，然后按照这个顺序，用类似“动态规划”的方式，只需一次遍历就能计算出所有最短路径。这极大地提高了效率。

核心思想：
在拓扑排序中，对于任意一条有向边 (u -> v)，u 一定出现在 v 之前。这意味着，当我们处理顶点 u 时，所有能到达 u 的顶点的最短距离必然已经计算完毕。那么，当我们要更新 u 的后继顶点 v 的最短距离时，u 自身的 dist[u] 已经是最优解，不会再被其后续节点影响。这保证了“无后效性”。

算法步骤详解

我们以一个具体的DAG为例讲解。假设我们有如下有向无环图，源点为 0：

顶点: 0, 1, 2, 3, 4
边及权重:
0 -> 1, 5
0 -> 2, 3
1 -> 2, 2
1 -> 3, 6
2 -> 3, 7
2 -> 4, 4
3 -> 4, 2

（你可以想象这个图描述了一个项目的工作流，边权代表完成前一个任务到后一个任务所需时间，我们的目标是计算从任务0开始，最早何时能完成其他所有任务。实际上这就是“关键路径”计算最早开始时间的部分）。

步骤1：对图进行拓扑排序

拓扑排序是算法的基础。其目标是生成一个顶点的线性序列，使得对于图中的每一条有向边 (u -> v)，u 在序列中都出现在 v 之前。

实现方法（Kahn算法或DFS后序遍历）：
这里我们使用Kahn算法，因为它能自然地检测环（虽然题目保证是DAG），并且实现直观。

计算每个顶点的入度（指向该顶点的边的数量）。
将所有入度为0的顶点加入一个队列。
当队列非空时：
a. 从队列中取出一个顶点 u，将其加入拓扑序列。
b. 对于 u 的每一个后继顶点 v：
将 v 的入度减1。如果减1后 v 的入度变为0，则将 v 加入队列。

对于我们例子中的图：

初始入度：[0: 0, 1: 1, 2: 2, 3: 2, 4: 2]
拓扑排序过程：
1. 队列初始为 [0]，出队0，拓扑序: [0]。更新后继1,2的入度，变为[1:0], [2:1]。将入度为0的1入队。
2. 队列为 [1]，出队1，拓扑序: [0, 1]。更新后继2,3的入度，变为[2:0], [3:1]。将2入队。
3. 队列为 [2]，出队2，拓扑序: [0, 1, 2]。更新后继3,4的入度，变为[3:0], [4:1]。将3入队。
4. 队列为 [3]，出队3，拓扑序: [0, 1, 2, 3]。更新后继4的入度，变为[4:0]。将4入队。
5. 队列为 [4]，出队4，拓扑序: [0, 1, 2, 3, 4]。

最终得到拓扑序：[0, 1, 2, 3, 4]。

步骤2：初始化距离数组

创建一个大小为 V（顶点数）的数组 dist[]，用于存储从源点 s 到每个顶点的最短距离。

将 dist[s] 初始化为 0，因为从源点到自身的距离为0。
将其他所有顶点的 dist 初始化为 ∞（用一个非常大的数表示，例如 INF）。

对于我们的例子（s=0）：

dist = [0, INF, INF, INF, INF]

步骤3：按拓扑序进行“松弛”操作

这是算法的核心。我们按照步骤1得到的拓扑顺序，依次处理每个顶点 u。

对于每个顶点 u：

如果 dist[u] != INF（即当前顶点是可达的），则处理其所有出边。
对于每条以 u 为起点的边 (u -> v)，权重为 weight，尝试“松弛”：
- 新的候选距离是 dist[u] + weight。
- 如果 dist[u] + weight < dist[v]，则更新 dist[v] = dist[u] + weight。

为什么按拓扑序处理是正确的？
因为当处理到顶点 u 时，所有能到达 u 的顶点（即 u 的“前辈”）都已经被处理过了（因为它们都出现在拓扑序中 u 的前面）。因此，dist[u] 此时已经是从源点到 u 的最终最短距离，不可能再被后续的更新所减小。这样，我们就可以用这个“确定”的最短距离去更新 u 的后继节点。

让我们手动模拟过程：

拓扑序: [0, 1, 2, 3, 4]

处理 u = 0：
- dist[0] = 0（可达）。
- 边 (0->1, 5)：dist[1] = min(INF, 0+5) = 5
- 边 (0->2, 3)：dist[2] = min(INF, 0+3) = 3
- 当前 dist = [0, 5, 3, INF, INF]
处理 u = 1：
- dist[1] = 5（可达）。
- 边 (1->2, 2)：dist[2] = min(3, 5+2) = 3（保持3，因为3<7）
- 边 (1->3, 6)：dist[3] = min(INF, 5+6) = 11
- 当前 dist = [0, 5, 3, 11, INF]
处理 u = 2：
- dist[2] = 3（可达）。
- 边 (2->3, 7)：dist[3] = min(11, 3+7) = 10
- 边 (2->4, 4)：dist[4] = min(INF, 3+4) = 7
- 当前 dist = [0, 5, 3, 10, 7]
处理 u = 3：
- dist[3] = 10（可达）。
- 边 (3->4, 2)：dist[4] = min(7, 10+2) = 7（保持7，因为7<12）
- 当前 dist = [0, 5, 3, 10, 7]
处理 u = 4：
- dist[4] = 7（可达）。但它没有出边，无需处理。

最终结果：
dist = [0, 5, 3, 10, 7]

这意味着从源点0到各点的最短距离为：

到0: 0
到1: 5
到2: 3
到3: 10
到4: 7

步骤4：路径重建（如果需要）

如果问题要求输出具体的最短路径，而不仅仅是距离，我们可以在松弛操作的同时，用一个 prev[] 数组记录“前驱节点”。

初始化时，所有 prev[v] = -1 或 None。
在松弛操作中，每当 dist[v] 被更新时，就设置 prev[v] = u。

在算法结束后，对于任意顶点 v，从后向前依次访问 prev[v] 直到遇到源点 s，再将序列反转，即可得到从 s 到 v 的最短路径。

在我们例子中，prev 数组最终会是：

prev = [None, 0, 0, 2, 2]

解释：

到顶点1的最短路径：1 <- 0，即路径 0->1
到顶点2的最短路径：2 <- 0，即路径 0->2
到顶点3的最短路径：3 <- 2 <- 0，即路径 0->2->3
到顶点4的最短路径：4 <- 2 <- 0，即路径 0->2->4

算法复杂度分析

时间复杂度：O(V + E)
- 拓扑排序：O(V + E)
- 初始化：O(V)
- 按拓扑序松弛：每个顶点和每条边都被处理一次，O(V + E)
空间复杂度：O(V)，用于存储入度数组、距离数组、拓扑序列队列。

这比 Bellman-Ford 算法的 O(VE) 要高效得多，尤其适用于稀疏图。

关键要点与思考

DAG特性是前提：算法强烈依赖于图的拓扑序。如果图中存在环，此算法不适用。实际应用中，有时需要对任务依赖图等DAG进行最早/最晚时间计算，此算法是理论基础。
处理负权边：这是本算法相对于Dijkstra算法的主要优势。DAG的结构保证了即使有负权边，也不会陷入无限循环，因为路径不可能循环地越来越短。
与“最长路径”的关系：如果将所有权重取负值，然后运行此算法，得到的最短路径就是原图的最长路径。所以DAG中的最长路径问题也可以用此算法解决。
实际应用：除了项目管理（关键路径法），在编译优化（指令调度）、数据序列化、解决具有依赖关系的动态规划问题等方面都有应用。

这个算法完美展示了如何利用图的结构特性（无环），将一般性的算法（动态规划思想）与特定的图操作（拓扑排序）结合起来，得到一种既高效又简单的解决方案。

有向无环图（DAG）中的单源最短路径问题（拓扑排序解法）我将为你讲解“有向无环图（DAG）中的单源最短路径问题”及其基于拓扑排序的解法。这个问题是图论中一个重要的基础算法，它利用DAG的特性，提供了比通用算法更高效的解决方案。问题描述给定一个有向无环图（DAG），图中每条边都有一个权重（可以是正数、负数或零）。同时指定一个源点 s 。我们的目标是找出从源点 s 到图中所有其他顶点的最短路径距离。关键特点：图是有向的，且无环。这意味着图中不存在从一个顶点出发最终又能回到该顶点的有向路径。边的权重可以是负数。这与Dijkstra算法（不能处理负权边）形成对比。由于图中无环，也就不可能存在负权环，因此最短路径总是良定义的，不会出现“无穷小”的情况。目标输出：一个数组 dist[] ，其中 dist[v] 表示从源点 s 到顶点 v 的最短路径距离。如果从 s 无法到达 v ，则 dist[v] = ∞ 。为什么这个问题特殊？在通用有向图中，解决单源最短路径问题通常使用： Bellman-Ford算法：时间复杂度 O(VE)，可处理负权边，并能检测负权环。 SPFA算法：Bellman-Ford的队列优化，最坏复杂度仍是O(VE)。然而，由于DAG具有线性顺序（拓扑序）这一优良性质，我们可以先对图进行拓扑排序，然后按照这个顺序，用类似“动态规划”的方式，只需一次遍历就能计算出所有最短路径。这极大地提高了效率。核心思想：在拓扑排序中，对于任意一条有向边 (u -> v) ， u 一定出现在 v 之前。这意味着，当我们处理顶点 u 时，所有能到达 u 的顶点的最短距离必然已经计算完毕。那么，当我们要更新 u 的后继顶点 v 的最短距离时， u 自身的 dist[u] 已经是最优解，不会再被其后续节点影响。这保证了“无后效性”。算法步骤详解我们以一个具体的DAG为例讲解。假设我们有如下有向无环图，源点为 0 ：（你可以想象这个图描述了一个项目的工作流，边权代表完成前一个任务到后一个任务所需时间，我们的目标是计算从任务0开始，最早何时能完成其他所有任务。实际上这就是“关键路径”计算最早开始时间的部分）。步骤1：对图进行拓扑排序拓扑排序是算法的基础。其目标是生成一个顶点的线性序列，使得对于图中的每一条有向边 (u -> v) ， u 在序列中都出现在 v 之前。实现方法（Kahn算法或DFS后序遍历）：这里我们使用Kahn算法，因为它能自然地检测环（虽然题目保证是DAG），并且实现直观。计算每个顶点的入度（指向该顶点的边的数量）。将所有入度为0的顶点加入一个队列。当队列非空时： a. 从队列中取出一个顶点 u ，将其加入拓扑序列。 b. 对于 u 的每一个后继顶点 v ：将 v 的入度减1。如果减1后 v 的入度变为0，则将 v 加入队列。对于我们例子中的图：初始入度： [0: 0, 1: 1, 2: 2, 3: 2, 4: 2] 拓扑排序过程：队列初始为 [0] ，出队0，拓扑序: [0] 。更新后继 1 , 2 的入度，变为 [1:0] , [2:1] 。将入度为0的 1 入队。队列为 [1] ，出队1，拓扑序: [0, 1] 。更新后继 2 , 3 的入度，变为 [2:0] , [3:1] 。将 2 入队。队列为 [2] ，出队2，拓扑序: [0, 1, 2] 。更新后继 3 , 4 的入度，变为 [3:0] , [4:1] 。将 3 入队。队列为 [3] ，出队3，拓扑序: [0, 1, 2, 3] 。更新后继 4 的入度，变为 [4:0] 。将 4 入队。队列为 [4] ，出队4，拓扑序: [0, 1, 2, 3, 4] 。最终得到拓扑序： [0, 1, 2, 3, 4] 。步骤2：初始化距离数组创建一个大小为 V （顶点数）的数组 dist[] ，用于存储从源点 s 到每个顶点的最短距离。将 dist[s] 初始化为 0 ，因为从源点到自身的距离为0。将其他所有顶点的 dist 初始化为 ∞ （用一个非常大的数表示，例如 INF ）。对于我们的例子（ s=0 ）：步骤3：按拓扑序进行“松弛”操作这是算法的核心。我们按照步骤1得到的拓扑顺序，依次处理每个顶点 u 。对于每个顶点 u ：如果 dist[u] != INF （即当前顶点是可达的），则处理其所有出边。对于每条以 u 为起点的边 (u -> v) ，权重为 weight ，尝试“松弛”：新的候选距离是 dist[u] + weight 。如果 dist[u] + weight < dist[v] ，则更新 dist[v] = dist[u] + weight 。为什么按拓扑序处理是正确的？因为当处理到顶点 u 时，所有能到达 u 的顶点（即 u 的“前辈”）都已经被处理过了（因为它们都出现在拓扑序中 u 的前面）。因此， dist[u] 此时已经是从源点到 u 的最终最短距离，不可能再被后续的更新所减小。这样，我们就可以用这个“确定”的最短距离去更新 u 的后继节点。让我们手动模拟过程：拓扑序: [ 0, 1, 2, 3, 4] 处理 u = 0 ： dist[0] = 0 （可达）。边 (0->1, 5) ： dist[1] = min(INF, 0+5) = 5 边 (0->2, 3) ： dist[2] = min(INF, 0+3) = 3 当前 dist = [0, 5, 3, INF, INF] 处理 u = 1 ： dist[1] = 5 （可达）。边 (1->2, 2) ： dist[2] = min(3, 5+2) = 3 （保持3，因为3 <7）边 (1->3, 6) ： dist[3] = min(INF, 5+6) = 11 当前 dist = [0, 5, 3, 11, INF] 处理 u = 2 ： dist[2] = 3 （可达）。边 (2->3, 7) ： dist[3] = min(11, 3+7) = 10 边 (2->4, 4) ： dist[4] = min(INF, 3+4) = 7 当前 dist = [0, 5, 3, 10, 7] 处理 u = 3 ： dist[3] = 10 （可达）。边 (3->4, 2) ： dist[4] = min(7, 10+2) = 7 （保持7，因为7 <12）当前 dist = [0, 5, 3, 10, 7] 处理 u = 4 ： dist[4] = 7 （可达）。但它没有出边，无需处理。最终结果： dist = [0, 5, 3, 10, 7] 这意味着从源点0到各点的最短距离为：到0: 0 到1: 5 到2: 3 到3: 10 到4: 7 步骤4：路径重建（如果需要）如果问题要求输出具体的最短路径，而不仅仅是距离，我们可以在松弛操作的同时，用一个 prev[] 数组记录“前驱节点”。初始化时，所有 prev[v] = -1 或 None 。在松弛操作中，每当 dist[v] 被更新时，就设置 prev[v] = u 。在算法结束后，对于任意顶点 v ，从后向前依次访问 prev[v] 直到遇到源点 s ，再将序列反转，即可得到从 s 到 v 的最短路径。在我们例子中， prev 数组最终会是：解释：到顶点1的最短路径： 1 <- 0 ，即路径 0->1 到顶点2的最短路径： 2 <- 0 ，即路径 0->2 到顶点3的最短路径： 3 <- 2 <- 0 ，即路径 0->2->3 到顶点4的最短路径： 4 <- 2 <- 0 ，即路径 0->2->4 算法复杂度分析时间复杂度：O(V + E) 拓扑排序：O(V + E) 初始化：O(V) 按拓扑序松弛：每个顶点和每条边都被处理一次，O(V + E) 空间复杂度：O(V)，用于存储入度数组、距离数组、拓扑序列队列。这比 Bellman-Ford 算法的 O(VE) 要高效得多，尤其适用于稀疏图。关键要点与思考 DAG特性是前提：算法强烈依赖于图的拓扑序。如果图中存在环，此算法不适用。实际应用中，有时需要对任务依赖图等DAG进行最早/最晚时间计算，此算法是理论基础。处理负权边：这是本算法相对于Dijkstra算法的主要优势。DAG的结构保证了即使有负权边，也不会陷入无限循环，因为路径不可能循环地越来越短。与“最长路径”的关系：如果将所有权重取负值，然后运行此算法，得到的最短路径就是原图的最长路径。所以DAG中的最长路径问题也可以用此算法解决。实际应用：除了项目管理（关键路径法），在编译优化（指令调度）、数据序列化、解决具有依赖关系的动态规划问题等方面都有应用。这个算法完美展示了如何利用图的结构特性（无环），将一般性的算法（动态规划思想）与特定的图操作（拓扑排序）结合起来，得到一种既高效又简单的解决方案。