寻找有向无环图（DAG）中的关键路径算法

字数 3057 2025-12-12 02:05:32

寻找有向无环图（DAG）中的关键路径算法

题目描述

给定一个有向无环图（DAG），图中的每个顶点代表一个任务，每条有向边代表任务间的依赖关系，即箭头起点的任务完成后，箭头终点的任务才能开始。此外，每个顶点有一个权重，代表完成该任务所需的时间。请设计一个算法，找出这个DAG中的"关键路径"——即从起点到终点的最长加权路径。关键路径的长度决定了整个项目的最短完成时间，路径上的任何任务延迟都会导致项目总时间的延迟。

解题过程

第一步：问题理解与建模

输入是一个DAG，顶点数为 \(V\)，边数为 \(E\)。
每个顶点 \(v_i\) 有一个权值 \(\text{duration}[i]\)，表示任务耗时。
依赖关系由有向边表示：如果存在边 \(u \to v\)，则任务 \(u\) 完成后，任务 \(v\) 才能开始。
目标是找到从源点（入度为0的顶点）到汇点（出度为0的顶点）的最长加权路径。
注意：DAG可能有多个源点和汇点，通常可以通过添加一个"超级源点"（指向所有原入度为0的点）和"超级汇点"（被所有原出度为0的点指向），且这两个点的权值为0，从而转化为单源单汇问题。为简化，我们假设图中只有一个源点和一个汇点。

第二步：核心思路——动态规划与拓扑排序

由于图是无环的，我们可以按照拓扑顺序处理顶点，确保在处理一个顶点时，其所有前驱任务都已经处理完毕。关键路径问题可以通过动态规划求解：

定义两个数组：
- \(\text{earliest}[i]\)：表示任务 \(i\) 可能的最早开始时间。
- \(\text{latest}[i]\)：表示任务 \(i\) 在不延误总工期的前提下，最晚必须开始的时间。
关键路径由满足 \(\text{earliest}[i] = \text{latest}[i]\) 的任务组成，这些任务没有时间余量，任何延迟都会影响总工期。

第三步：算法步骤

步骤1：拓扑排序

使用 Kahn 算法或 DFS 对 DAG 进行拓扑排序，得到顶点顺序列表 topo_order。
拓扑排序确保我们总是先处理前驱，再处理后继。

步骤2：计算最早开始时间（正向传播）

初始化：对于源点 \(s\)，设置 \(\text{earliest}[s] = 0\)。
按照 topo_order 的顺序遍历每个顶点 \(u\)：
- 对于 \(u\) 的每个后继 \(v\)（即边 \(u \to v\)）：
  - 更新 \(\text{earliest}[v] = \max(\text{earliest}[v], \text{earliest}[u] + \text{duration}[u])\)。
- 解释：任务 \(v\) 必须在所有前置任务完成后才能开始，所以取所有前置任务完成时间的最大值。
最终，整个项目的最短完成时间 \(T = \text{earliest}[t] + \text{duration}[t]\)，其中 \(t\) 是汇点（因为汇点任务的持续时间也需要加上）。

步骤3：计算最晚开始时间（反向传播）

初始化：对于汇点 \(t\)，设置 \(\text{latest}[t] = T - \text{duration}[t]\)。（因为汇点必须在时间 \(T\) 完成，所以其最晚开始时间不能晚于 \(T - \text{duration}[t]\)）。
按照 topo_order 的逆序遍历每个顶点 \(v\)：
- 对于 \(v\) 的每个前驱 \(u\)（即边 \(u \to v\)）：
  - 更新 \(\text{latest}[u] = \min(\text{latest}[u], \text{latest}[v] - \text{duration}[u])\)。
- 解释：任务 \(u\) 必须足够早开始，以确保其后继任务 \(v\) 能按时完成，所以取所有后继任务的最晚开始时间减去 \(u\) 的耗时中的最小值。

步骤4：确定关键任务与关键路径

对于每个顶点 \(i\)，计算其时间余量（slack）或浮动时间：\(\text{float}[i] = \text{latest}[i] - \text{earliest}[i]\)。
若 \(\text{float}[i] == 0\)，则任务 \(i\) 为关键任务。
关键路径是关键任务构成的一条（或多条）从源点到汇点的路径。可以通过从源点开始，仅沿着关键任务向后遍历（选择满足 \(\text{earliest}[v] = \text{earliest}[u] + \text{duration}[u]\) 且 \(\text{float}[v] == 0\) 的后继 \(v\)）来重建一条关键路径。

第四步：实例说明

考虑一个简单的DAG，顶点为A(3), B(2), C(4), D(1)，边为 A→B, A→C, B→D, C→D。

源点为A，汇点为D，权值括号内。

拓扑排序：假设为 [A, B, C, D]。

正向计算最早开始时间：

earliest[A] = 0
A→B: earliest[B] = max(0, 0+3) = 3
A→C: earliest[C] = max(0, 0+3) = 3
B→D: earliest[D] = max(0, 3+2) = 5
C→D: earliest[D] = max(5, 3+4) = 7
最终 T = earliest[D] + duration[D] = 7 + 1 = 8

反向计算最晚开始时间：

latest[D] = T - duration[D] = 8 - 1 = 7
D的前驱B：latest[B] = min(∞, 7 - 2) = 5
D的前驱C：latest[C] = min(∞, 7 - 4) = 3
B的前驱A：latest[A] = min(∞, 5 - 3) = 2
C的前驱A：latest[A] = min(2, 3 - 3) = 0

计算时间余量：

float[A] = 0 - 0 = 0 (关键)
float[B] = 5 - 3 = 2 (非关键)
float[C] = 3 - 3 = 0 (关键)
float[D] = 7 - 7 = 0 (关键)

关键路径：A → C → D，总长度为 3 + 4 + 1 = 8。

第五步：复杂度分析

拓扑排序：\(O(V + E)\)
正向与反向传播：每个顶点和每条边各访问一次，也是 \(O(V + E)\)
重建关键路径：\(O(V + E)\)
总时间复杂度为 \(O(V + E)\)，空间复杂度为 \(O(V)\) 存储数组。

第六步：扩展与应用

若存在多个源点/汇点，按前述方法添加超级源点/汇点即可。
关键路径法（CPM）在项目管理中广泛应用，可帮助识别关键任务以优化资源分配。
如果任务有时间窗或资源约束，问题会变得更加复杂，可能需要更高级的调度算法。

寻找有向无环图（DAG）中的关键路径算法题目描述给定一个有向无环图（DAG），图中的每个顶点代表一个任务，每条有向边代表任务间的依赖关系，即箭头起点的任务完成后，箭头终点的任务才能开始。此外，每个顶点有一个权重，代表完成该任务所需的时间。请设计一个算法，找出这个DAG中的"关键路径"——即从起点到终点的最长加权路径。关键路径的长度决定了整个项目的最短完成时间，路径上的任何任务延迟都会导致项目总时间的延迟。解题过程第一步：问题理解与建模输入是一个DAG，顶点数为 \( V \)，边数为 \( E \)。每个顶点 \( v_ i \) 有一个权值 \( \text{duration}[ i ] \)，表示任务耗时。依赖关系由有向边表示：如果存在边 \( u \to v \)，则任务 \( u \) 完成后，任务 \( v \) 才能开始。目标是找到从源点（入度为0的顶点）到汇点（出度为0的顶点）的最长加权路径。注意：DAG可能有多个源点和汇点，通常可以通过添加一个"超级源点"（指向所有原入度为0的点）和"超级汇点"（被所有原出度为0的点指向），且这两个点的权值为0，从而转化为单源单汇问题。为简化，我们假设图中只有一个源点和一个汇点。第二步：核心思路——动态规划与拓扑排序由于图是无环的，我们可以按照拓扑顺序处理顶点，确保在处理一个顶点时，其所有前驱任务都已经处理完毕。关键路径问题可以通过动态规划求解：定义两个数组： \( \text{earliest}[ i ] \)：表示任务 \( i \) 可能的最早开始时间。 \( \text{latest}[ i ] \)：表示任务 \( i \) 在不延误总工期的前提下，最晚必须开始的时间。关键路径由满足 \( \text{earliest}[ i] = \text{latest}[ i ] \) 的任务组成，这些任务没有时间余量，任何延迟都会影响总工期。第三步：算法步骤步骤1：拓扑排序使用 Kahn 算法或 DFS 对 DAG 进行拓扑排序，得到顶点顺序列表 topo_order 。拓扑排序确保我们总是先处理前驱，再处理后继。步骤2：计算最早开始时间（正向传播）初始化：对于源点 \( s \)，设置 \( \text{earliest}[ s ] = 0 \)。按照 topo_order 的顺序遍历每个顶点 \( u \)：对于 \( u \) 的每个后继 \( v \)（即边 \( u \to v \)）：更新 \( \text{earliest}[ v] = \max(\text{earliest}[ v], \text{earliest}[ u] + \text{duration}[ u ]) \)。解释：任务 \( v \) 必须在所有前置任务完成后才能开始，所以取所有前置任务完成时间的最大值。最终，整个项目的最短完成时间 \( T = \text{earliest}[ t] + \text{duration}[ t ] \)，其中 \( t \) 是汇点（因为汇点任务的持续时间也需要加上）。步骤3：计算最晚开始时间（反向传播）初始化：对于汇点 \( t \)，设置 \( \text{latest}[ t] = T - \text{duration}[ t] \)。（因为汇点必须在时间 \( T \) 完成，所以其最晚开始时间不能晚于 \( T - \text{duration}[ t ] \)）。按照 topo_order 的逆序遍历每个顶点 \( v \)：对于 \( v \) 的每个前驱 \( u \)（即边 \( u \to v \)）：更新 \( \text{latest}[ u] = \min(\text{latest}[ u], \text{latest}[ v] - \text{duration}[ u ]) \)。解释：任务 \( u \) 必须足够早开始，以确保其后继任务 \( v \) 能按时完成，所以取所有后继任务的最晚开始时间减去 \( u \) 的耗时中的最小值。步骤4：确定关键任务与关键路径对于每个顶点 \( i \)，计算其时间余量（slack）或浮动时间：\( \text{float}[ i] = \text{latest}[ i] - \text{earliest}[ i ] \)。若 \( \text{float}[ i ] == 0 \)，则任务 \( i \) 为关键任务。关键路径是关键任务构成的一条（或多条）从源点到汇点的路径。可以通过从源点开始，仅沿着关键任务向后遍历（选择满足 \( \text{earliest}[ v] = \text{earliest}[ u] + \text{duration}[ u] \) 且 \( \text{float}[ v ] == 0 \) 的后继 \( v \)）来重建一条关键路径。第四步：实例说明考虑一个简单的DAG，顶点为A(3), B(2), C(4), D(1)，边为 A→B, A→C, B→D, C→D。源点为A，汇点为D，权值括号内。拓扑排序：假设为 [ A, B, C, D ]。正向计算最早开始时间： earliest[ A ] = 0 A→B: earliest[ B ] = max(0, 0+3) = 3 A→C: earliest[ C ] = max(0, 0+3) = 3 B→D: earliest[ D ] = max(0, 3+2) = 5 C→D: earliest[ D ] = max(5, 3+4) = 7 最终 T = earliest[ D] + duration[ D ] = 7 + 1 = 8 反向计算最晚开始时间： latest[ D] = T - duration[ D ] = 8 - 1 = 7 D的前驱B：latest[ B ] = min(∞, 7 - 2) = 5 D的前驱C：latest[ C ] = min(∞, 7 - 4) = 3 B的前驱A：latest[ A ] = min(∞, 5 - 3) = 2 C的前驱A：latest[ A ] = min(2, 3 - 3) = 0 计算时间余量： float[ A ] = 0 - 0 = 0 (关键) float[ B ] = 5 - 3 = 2 (非关键) float[ C ] = 3 - 3 = 0 (关键) float[ D ] = 7 - 7 = 0 (关键) 关键路径：A → C → D，总长度为 3 + 4 + 1 = 8。第五步：复杂度分析拓扑排序：\( O(V + E) \) 正向与反向传播：每个顶点和每条边各访问一次，也是 \( O(V + E) \) 重建关键路径：\( O(V + E) \) 总时间复杂度为 \( O(V + E) \)，空间复杂度为 \( O(V) \) 存储数组。第六步：扩展与应用若存在多个源点/汇点，按前述方法添加超级源点/汇点即可。关键路径法（CPM）在项目管理中广泛应用，可帮助识别关键任务以优化资源分配。如果任务有时间窗或资源约束，问题会变得更加复杂，可能需要更高级的调度算法。