有向无环图（DAG）中最长路径的动态规划解法
字数 2563 2025-12-13 19:11:35

有向无环图（DAG）中最长路径的动态规划解法

问题描述

给定一个有向无环图（DAG），其中每个边都有一个权重（可以是正数、负数或零），我们需要找到从任意源点到任意终点的最长路径的长度。由于图是无环的，这个问题可以通过动态规划高效解决，而不会陷入正权环的无限循环。

这个问题在实际中有很多应用，比如：

  • 项目调度中的关键路径分析。
  • 计算依赖任务的最长完成时间。
  • 编译器中的指令调度。

我们假设图以邻接表形式给出，每个节点从0到n-1编号。

解题步骤

步骤1：理解DAG的性质

在DAG中，由于没有环，我们可以对节点进行拓扑排序。拓扑排序是指将图中的所有节点排成一个线性序列，使得对于图中的每一条有向边(u, v)，节点u在序列中都出现在节点v之前。这个性质是动态规划解法的基础，因为它确保了当我们计算某个节点的最长路径时，所有可能到达它的节点的最长路径都已经被计算出来。

步骤2：拓扑排序

首先，我们需要对DAG进行拓扑排序。常用的方法有两种：

  • Kahn算法：基于入度（indegree）的广度优先搜索。
  • 深度优先搜索（DFS）的后序遍历：在DFS遍历中，当一个节点所有后继都访问完毕后，将其加入栈中，最后栈中节点从栈顶到栈底就是拓扑排序结果。

这里我们采用Kahn算法，因为它可以自然地按拓扑顺序处理节点。

算法过程：

  1. 计算每个节点的入度（indegree），即有多少条边指向该节点。
  2. 将所有入度为0的节点加入一个队列。
  3. 当队列非空时：
    a. 弹出队首节点u。
    b. 将u加入拓扑排序结果列表。
    c. 对于u的每个邻居v，将其入度减1。如果减1后v的入度变为0，则将v加入队列。
  4. 如果结果列表中的节点数等于总节点数n，则拓扑排序成功；否则图中存在环（与DAG假设矛盾）。

步骤3：动态规划状态定义

设 dp[i] 表示从某个起点（或多个起点）到达节点i的最长路径长度。注意，这里的“起点”并不固定；我们最终要找的是整个图中所有可能路径中的最大值。

为了计算 dp[i]，我们可以利用拓扑排序的顺序：对于每个节点i，我们考虑所有可能的前驱节点j（即存在边从j指向i），那么到达i的最长路径可能是通过某个前驱j的路径加上边(j, i)的权重。

因此，状态转移方程为：
dp[i] = max( dp[j] + weight(j, i) )，其中j是所有指向i的前驱节点。

如果没有前驱（即入度为0），那么 dp[i] 初始化为0（如果允许路径长度为0）或负无穷（如果要求路径至少包含一条边，则无前驱的节点不可达，初始化为负无穷）。

步骤4：初始化与计算顺序

初始化：所有节点的 dp 值初始化为负无穷（-∞），因为我们需要找最大值，且允许负权重边。

但是，如果我们允许路径长度为0（即路径可以只包含一个节点），那么对于每个节点，我们可以将其 dp 值初始化为0，因为从该节点自身出发到自身的路径长度为0。不过，在最长路径问题中，通常我们关注的是至少包含一条边的路径，所以常见做法是：

  • 将所有入度为0的节点（源点）的 dp 值初始化为0。
  • 其他节点初始化为负无穷。

这样，只有从某个源点可达的路径才会被考虑。

计算顺序：按照拓扑排序的顺序依次处理每个节点。当我们处理节点i时，它的所有前驱j都已经在拓扑排序中先于i被处理，因此 dp[j] 已经计算完成，可以直接用于更新 dp[i]。

步骤5：算法流程

  1. 拓扑排序：使用Kahn算法得到拓扑顺序列表 topo_order。
  2. 初始化dp数组：
    • 创建数组 dp，长度为n，初始值全部设为负无穷（例如 -inf）。
    • 遍历所有节点，对于每个入度为0的节点u，设置 dp[u] = 0（因为从u自身开始，路径长度为0）。
  3. 动态规划递推：
    • 按照 topo_order 的顺序遍历每个节点u。
    • 对于u的每个邻居v（即存在有向边 u -> v，权重为w）：
      • 尝试更新 dp[v] = max( dp[v], dp[u] + w )。
  4. 获取结果：
    • 最长路径的长度就是 dp 数组中的最大值，即 max(dp)。

步骤6：例子说明

考虑一个简单的DAG：
节点：0, 1, 2, 3
边：(0->1, 5), (0->2, 3), (1->3, 2), (2->3, 7)
拓扑排序可能是 [0, 1, 2, 3] 或 [0, 2, 1, 3]。

初始化：
入度为0的节点：0，所以 dp = [0, -∞, -∞, -∞]。

按拓扑顺序处理：

  • 处理节点0：更新邻居。
    • 更新节点1：dp[1] = max(-∞, 0+5) = 5。
    • 更新节点2：dp[2] = max(-∞, 0+3) = 3。
  • 处理节点1：更新邻居。
    • 更新节点3：dp[3] = max(-∞, 5+2) = 7。
  • 处理节点2：更新邻居。
    • 更新节点3：dp[3] = max(7, 3+7) = 10。
  • 处理节点3：无邻居。

最终 dp = [0, 5, 3, 10]，最长路径长度为10（路径 0->2->3）。

步骤7：复杂度分析

  • 拓扑排序：O(V + E)，其中V是顶点数，E是边数。
  • 动态规划递推：遍历每个节点和每条边，也是O(V + E)。
    总时间复杂度为 O(V + E)，非常高效。

步骤8：边界情况与扩展

  • 负权重边：由于图是无环的，动态规划可以正确处理负权重边，不会像Dijkstra算法那样失效。
  • 多个源点：算法自动处理多个入度为0的节点作为起点。
  • 路径重建：如果需要输出具体路径，可以维护一个 predecessor 数组，记录每个节点在最长路径中的前驱节点。在更新 dp[v] 时，如果 dp[u] + w > dp[v]，则设置 pred[v] = u。最后从最大 dp 值的节点反向追溯即可。
  • 最长路径与最短路径：如果将所有权重取负，那么最长路径问题就变成了最短路径问题，可以用同样的方法求解（即DAG上的最短路径动态规划，也称为“临界路径”的变种）。

这个算法充分利用了DAG的无环性质，通过拓扑排序确保了动态规划的无后效性，是解决DAG上最长（或最短）路径问题的标准方法。

有向无环图（DAG）中最长路径的动态规划解法 问题描述 给定一个有向无环图（DAG），其中每个边都有一个权重（可以是正数、负数或零），我们需要找到从任意源点到任意终点的最长路径的长度。由于图是无环的，这个问题可以通过动态规划高效解决，而不会陷入正权环的无限循环。 这个问题在实际中有很多应用，比如： 项目调度中的关键路径分析。 计算依赖任务的最长完成时间。 编译器中的指令调度。 我们假设图以邻接表形式给出，每个节点从0到n-1编号。 解题步骤 步骤1：理解DAG的性质 在DAG中，由于没有环，我们可以对节点进行拓扑排序。拓扑排序是指将图中的所有节点排成一个线性序列，使得对于图中的每一条有向边(u, v)，节点u在序列中都出现在节点v之前。这个性质是动态规划解法的基础，因为它确保了当我们计算某个节点的最长路径时，所有可能到达它的节点的最长路径都已经被计算出来。 步骤2：拓扑排序 首先，我们需要对DAG进行拓扑排序。常用的方法有两种： Kahn算法 ：基于入度（indegree）的广度优先搜索。 深度优先搜索（DFS）的后序遍历 ：在DFS遍历中，当一个节点所有后继都访问完毕后，将其加入栈中，最后栈中节点从栈顶到栈底就是拓扑排序结果。 这里我们采用Kahn算法，因为它可以自然地按拓扑顺序处理节点。 算法过程： 计算每个节点的入度（indegree），即有多少条边指向该节点。 将所有入度为0的节点加入一个队列。 当队列非空时： a. 弹出队首节点u。 b. 将u加入拓扑排序结果列表。 c. 对于u的每个邻居v，将其入度减1。如果减1后v的入度变为0，则将v加入队列。 如果结果列表中的节点数等于总节点数n，则拓扑排序成功；否则图中存在环（与DAG假设矛盾）。 步骤3：动态规划状态定义 设 dp[i] 表示从某个起点（或多个起点）到达节点i的最长路径长度。注意，这里的“起点”并不固定；我们最终要找的是整个图中所有可能路径中的最大值。 为了计算 dp[i] ，我们可以利用拓扑排序的顺序：对于每个节点i，我们考虑所有可能的前驱节点j（即存在边从j指向i），那么到达i的最长路径可能是通过某个前驱j的路径加上边(j, i)的权重。 因此，状态转移方程为： dp[i] = max( dp[j] + weight(j, i) ) ，其中j是所有指向i的前驱节点。 如果没有前驱（即入度为0），那么 dp[i] 初始化为0（如果允许路径长度为0）或负无穷（如果要求路径至少包含一条边，则无前驱的节点不可达，初始化为负无穷）。 步骤4：初始化与计算顺序 初始化：所有节点的 dp 值初始化为负无穷（-∞），因为我们需要找最大值，且允许负权重边。 但是，如果我们允许路径长度为0（即路径可以只包含一个节点），那么对于每个节点，我们可以将其 dp 值初始化为0，因为从该节点自身出发到自身的路径长度为0。不过，在最长路径问题中，通常我们关注的是至少包含一条边的路径，所以常见做法是： 将所有入度为0的节点（源点）的 dp 值初始化为0。 其他节点初始化为负无穷。 这样，只有从某个源点可达的路径才会被考虑。 计算顺序：按照拓扑排序的顺序依次处理每个节点。当我们处理节点i时，它的所有前驱j都已经在拓扑排序中先于i被处理，因此 dp[j] 已经计算完成，可以直接用于更新 dp[i] 。 步骤5：算法流程 拓扑排序 ：使用Kahn算法得到拓扑顺序列表 topo_order 。 初始化dp数组 ： 创建数组 dp ，长度为n，初始值全部设为负无穷（例如 -inf）。 遍历所有节点，对于每个入度为0的节点u，设置 dp[u] = 0 （因为从u自身开始，路径长度为0）。 动态规划递推 ： 按照 topo_order 的顺序遍历每个节点u。 对于u的每个邻居v（即存在有向边 u -> v，权重为w）： 尝试更新 dp[v] = max( dp[v], dp[u] + w ) 。 获取结果 ： 最长路径的长度就是 dp 数组中的最大值，即 max(dp) 。 步骤6：例子说明 考虑一个简单的DAG： 节点：0, 1, 2, 3 边：(0->1, 5), (0->2, 3), (1->3, 2), (2->3, 7) 拓扑排序可能是 [ 0, 1, 2, 3] 或 [ 0, 2, 1, 3 ]。 初始化： 入度为0的节点：0，所以 dp = [ 0, -∞, -∞, -∞ ]。 按拓扑顺序处理： 处理节点0：更新邻居。 更新节点1：dp[ 1 ] = max(-∞, 0+5) = 5。 更新节点2：dp[ 2 ] = max(-∞, 0+3) = 3。 处理节点1：更新邻居。 更新节点3：dp[ 3 ] = max(-∞, 5+2) = 7。 处理节点2：更新邻居。 更新节点3：dp[ 3 ] = max(7, 3+7) = 10。 处理节点3：无邻居。 最终 dp = [ 0, 5, 3, 10 ]，最长路径长度为10（路径 0->2->3）。 步骤7：复杂度分析 拓扑排序：O(V + E)，其中V是顶点数，E是边数。 动态规划递推：遍历每个节点和每条边，也是O(V + E)。 总时间复杂度为 O(V + E)，非常高效。 步骤8：边界情况与扩展 负权重边 ：由于图是无环的，动态规划可以正确处理负权重边，不会像Dijkstra算法那样失效。 多个源点 ：算法自动处理多个入度为0的节点作为起点。 路径重建 ：如果需要输出具体路径，可以维护一个 predecessor 数组，记录每个节点在最长路径中的前驱节点。在更新 dp[v] 时，如果 dp[u] + w > dp[v] ，则设置 pred[v] = u 。最后从最大 dp 值的节点反向追溯即可。 最长路径与最短路径 ：如果将所有权重取负，那么最长路径问题就变成了最短路径问题，可以用同样的方法求解（即DAG上的最短路径动态规划，也称为“临界路径”的变种）。 这个算法充分利用了DAG的无环性质，通过拓扑排序确保了动态规划的无后效性，是解决DAG上最长（或最短）路径问题的标准方法。