寻找有向无环图（DAG）中的关键路径（Critical Path Method） 题目描述 给定一个有向无环图（DAG），图中每个顶点表示一个任务，每条有向边表示任务间的依赖关系，即前驱任务完成后才能开始后继任务。每个任务（顶点）都有一个完成所需的 持续时间 （顶点权重）。我们需要找出从 源点 （入度为0的顶点，表示项目的开始）到 汇点 （出度为0的顶点，表示项目的结束）的 最长路径 ，这条路径的长度（即路径上所有顶点持续时间的总和）决定了整个项目的最早完成时间，该路径被称为 关键路径 ，路径上的任务称为 关键任务 。任何关键任务的延迟都会导致整个项目延期。 目标 ：计算出整个项目的最早完成时间，并找出所有关键路径上的顶点（任务）。 注意 ：图中可能有多个入度为0的源点或多个出度为0的汇点，通常我们会通过添加一个“超级源点”连接到所有入度为0的顶点，以及一个“超级汇点”被所有出度为0的顶点连接，来统一处理。新添加的超级源点和超级汇点的持续时间为0。 解题过程循序渐进讲解 1. 问题理解与建模 将任务视为 顶点 ，任务间的依赖关系视为 有向边 ，每个顶点的权重是任务持续时间。 依赖关系：如果任务A必须在任务B开始前完成，则有一条有向边从A指向B。 由于依赖关系不能有循环（否则项目无法开始），图必须是有向无环图（DAG）。 关键路径是DAG中最长的加权路径（按顶点权重求和），它决定了项目的最短可能总工期。 2. 添加超级源点和超级汇点（处理多源多汇） 如果初始有多个入度为0的顶点，创建一个 超级源点S ，从S向每个入度为0的顶点添加一条有向边，S的持续时间为0。 如果初始有多个出度为0的顶点，创建一个 超级汇点T ，从每个出度为0的顶点向T添加一条有向边，T的持续时间为0。 这样，问题转化为从S到T的最长路径问题。 3. 计算最早开始时间（Forward Pass） 对DAG进行 拓扑排序 ，得到顶点的一个线性序列，使得所有有向边都从左指向右。 定义 earliest[u] 为顶点u的 最早开始时间 （即从源点S到u的最长路径长度）。 初始化： earliest[S] = 0 ，其他顶点为 -∞ （在计算中可用一个很小的负数表示，但实际中由于是DAG且从S出发可达，初始化为0也可，但需确保依赖更新）。 按拓扑顺序遍历每个顶点u： 对于u的每个后继顶点v，更新： earliest[v] = max(earliest[v], earliest[u] + duration[u]) 其中 duration[u] 是顶点u的持续时间。 注意：这里 earliest[v] 表示v可以开始的最早时间，而v的开始时间取决于所有前驱任务完成的最晚时间。 完成遍历后， earliest[T] 就是整个项目的 最早完成时间 （即关键路径长度）。 4. 计算最晚开始时间（Backward Pass） 定义 latest[u] 为顶点u在不延误整个项目的前提下，最晚必须开始的时间。 初始化： latest[T] = earliest[T] （汇点的最晚开始时间等于最早完成时间）。 按 逆拓扑顺序 遍历每个顶点u： 对于u的每个后继顶点v，更新： latest[u] = min(latest[u], latest[v] - duration[u]) 注意：u的最晚开始时间必须保证它的所有后继任务都能按时完成。 初始时 latest[u] 可设为一个很大的数（如∞），在遍历中不断减小。 完成遍历后，得到每个顶点的最晚开始时间。 5. 计算松弛时间并确定关键任务 定义顶点u的 松弛时间（Slack） 或 总浮动时间 为： slack[u] = latest[u] - earliest[u] 关键任务：松弛时间为0的任务，即 slack[u] == 0 。 关键路径：从源点S到汇点T，由所有关键任务构成的 任意一条最长路径 （可能有多条）。 可通过从S开始，沿着松弛时间为0的边（即满足 latest[v] - earliest[u] == duration[u] 的边(u,v)）进行深度优先搜索，找到所有到T的关键路径。 6. 算法步骤总结 构造DAG，添加超级源点S和超级汇点T（如果原图已有单源单汇则可跳过）。 对DAG进行拓扑排序。 正向传递：按拓扑序计算每个顶点的最早开始时间 earliest[] 。 反向传递：按逆拓扑序计算每个顶点的最晚开始时间 latest[] 。 计算每个顶点的松弛时间 slack[] ，松弛时间为0的顶点即为关键任务。 从S到T，沿着松弛时间为0的边，找出所有关键路径（可选）。 7. 复杂度分析 设顶点数n，边数m。 拓扑排序：O(n+m)。 正向/反向传递：每个顶点和边被访问一次，O(n+m)。 总复杂度：O(n+m)，即线性时间。 8. 实例演示（简化） 假设有4个任务A、B、C、D，持续时间分别为3、2、4、1，依赖关系：A→B，A→C，B→D，C→D。 添加超级源点S（0）指向A，超级汇点T（0）被B、C指向（注意：这里B、C不是出度为0，实际上D是汇点，但为简化，我们按原DAG计算，假设D是汇点，则S→A，D→T）。 为更清晰，我们直接用原图（A、B、C、D）计算，假设A是唯一源点，D是唯一汇点。 拓扑序：A、B、C、D。 正向传递： earliest[ A ]=0。 earliest[ B] = max(earliest[ B], earliest[ A ]+3) = 3。 earliest[ C] = max(earliest[ C], earliest[ A ]+3) = 3。 earliest[ D] = max(earliest[ D], earliest[ B]+2, earliest[ C ]+4) = max(?, 5, 7) = 7。 最早完成时间 = 7。 反向传递（初始化latest[ D ]=7）： latest[ D ]=7。 latest[ C] = min(latest[ C], latest[ D ]-4) = 3。 latest[ B] = min(latest[ B], latest[ D ]-2) = 5。 latest[ A] = min(latest[ A], latest[ B]-3, latest[ C ]-3) = min(∞, 2, 0) = 0。 松弛时间： slack[ A ] = 0-0=0； slack[ B ] = 5-3=2； slack[ C ] = 3-3=0； slack[ D ] = 7-7=0。 关键任务：A、C、D。 关键路径：A→C→D，长度为3+4=7。 通过以上步骤，我们就能精确找出DAG中的关键路径，从而管理项目进度。