关键路径算法（Critical Path Method）
字数 2857 2025-12-07 10:45:13

关键路径算法（Critical Path Method）

题目描述
在项目管理、任务调度等领域，我们常面对一个由一系列任务（或活动）构成的项目。每个任务有其预估完成所需时间（持续时间）。任务之间存在依赖关系，即某些任务必须在其他任务完成后才能开始。整个项目必须等所有任务都完成后才算结束。我们可以用一个有向无环图（DAG）来建模：

  • 每个顶点表示一个任务（或事件）。
  • 每条有向边 \(u \to v\) 表示任务 \(u\) 完成后才能开始任务 \(v\)。
  • 每条边（或任务顶点）可以关联一个权重，表示该任务的持续时间。

我们的目标是：

  1. 计算整个项目的最短完成时间（即从项目开始到结束的最长路径长度，因为所有前置任务必须完成）。
  2. 识别哪些任务是关键任务（critical activities）—— 即其任何延迟都会直接导致整个项目延期。
  3. 计算每个任务的最早开始时间、最晚开始时间、最早完成时间、最晚完成时间以及松弛时间（slack，即可延迟的时间而不影响项目完成）。

这就是关键路径算法（Critical Path Method, CPM）要解决的问题。

解题过程循序渐进讲解

步骤1：图的建模
为了统一处理，我们通常对DAG做以下转换：

  • 引入一个虚拟的起点（source）和终点（sink）。起点表示项目开始，它连接到所有没有前置任务的任务；所有没有后续任务的任务连接到终点。
  • 将任务持续时间放在顶点上（顶点表示任务），或者放在边上（边表示任务，顶点表示事件）。这里采用“顶点表示任务”的方式更直观。
  • 边只表示依赖关系，没有权重（或权重为0）。

例如，假设有任务A（持续3天）、B（持续2天）、C（持续4天）。依赖关系：A和B可同时开始，C必须在A和B都完成后才能开始。则图可建模为：
起点 → A → C → 终点
起点 → B → C → 终点
其中A、B、C顶点的权重是各自的持续时间。

步骤2：计算最早开始时间（Earliest Start Time, ES）
定义：ES[v] 表示任务v可以开始的最早时间（从项目开始时刻0起算）。
计算方法：对整个DAG进行拓扑排序，然后按拓扑序递推。

  • 对于起点（虚拟源点），ES[source] = 0。
  • 对于其他顶点v，考虑所有直接前驱u，则v必须等所有前驱u完成后才能开始。
    即 ES[v] = max_{u→v存在} (ES[u] + duration[u])，其中duration[u]是任务u的持续时间。

这是因为v必须等其所有前驱任务都完成才能开始，所以取最大值。

例子：
任务A（3天）、B（2天）、C（4天）、D（5天）。依赖：A→C, A→D, B→D。起点S，终点T。
拓扑序假设为 S, A, B, C, D, T。

  • ES[S] = 0
  • A的前驱只有S：ES[A] = 0 + 0 = 0
  • B的前驱只有S：ES[B] = 0 + 0 = 0
  • C的前驱是A：ES[C] = ES[A] + 3 = 3
  • D的前驱是A和B：ES[D] = max(ES[A]+3, ES[B]+2) = max(3,2) = 3
  • T的前驱是C和D：ES[T] = max(ES[C]+4, ES[D]+5) = max(7,8) = 8

因此项目最短完成时间 = ES[T] = 8 天。

步骤3：计算最晚开始时间（Latest Start Time, LS）
定义：LS[v] 表示任务v在不推迟项目完成时间的前提下，最晚必须开始的时间。
计算方法：在拓扑排序逆序（从终点向起点）递推。

  • 首先，设项目完成时间为 ES[T]，令 LS[T] = ES[T]（终点最晚开始等于最早开始）。
  • 对于其他顶点v，考虑其所有直接后继w，则v必须在不影响任何后继w的最晚开始前提下完成。
    即 LS[v] = min_{v→w存在} (LS[w] - duration[v])。

接上例：
已知 duration[A]=3, B=2, C=4, D=5。

  • LS[T] = ES[T] = 8
  • T的前驱是C和D：
    • LS[D] = LS[T] - duration[D] = 8 - 5 = 3
    • LS[C] = LS[T] - duration[C] = 8 - 4 = 4
  • D的前驱是A和B：
    • LS[A] 要考虑A的后继C和D：
      • 从C看：LS[A] ≤ LS[C] - duration[A] = 4 - 3 = 1
      • 从D看：LS[A] ≤ LS[D] - duration[A] = 3 - 3 = 0
        取 min(1,0) = 0
    • LS[B] 只需考虑后继D：LS[B] = LS[D] - duration[B] = 3 - 2 = 1
  • B的前驱是S：LS[S] 考虑后继A和B：
    • 从A看：LS[S] ≤ LS[A] - duration[S] = 0 - 0 = 0
    • 从B看：LS[S] ≤ LS[B] - duration[S] = 1 - 0 = 1
      取 min(0,1) = 0

步骤4：计算松弛时间（Slack / Float）
松弛时间 = LS[v] - ES[v]。
它表示任务v可以延迟多少时间开始，而不影响整个项目的最早完成时间。

  • 如果松弛时间为0，则该任务为关键任务（critical activity）。
  • 所有关键任务构成一条（或多条）从起点到终点的路径，称为关键路径（Critical Path）。

上例：

  • S: slack = 0-0=0（虚拟起点）
  • A: slack = 0-0=0 → 关键
  • B: slack = 1-0=1 → 非关键
  • C: slack = 4-3=1 → 非关键
  • D: slack = 3-3=0 → 关键
  • T: slack = 8-8=0（虚拟终点）

因此关键路径是 S → A → D → T，总时长 3+5 = 8 天。

步骤5：算法复杂度

  • 拓扑排序 O(V+E)。
  • 正向递推 ES：O(V+E)。
  • 反向递推 LS：O(V+E)。
  • 总体 O(V+E)，对稀疏图非常高效。

步骤6：实际应用注意事项

  1. 如果有多个起点或多个终点，添加虚拟源汇点。
  2. 如果存在“零持续时间”的依赖（仅表示顺序），可将其作为持续时间为0的任务，或直接用边表示。
  3. 关键路径可能有多条，所有松弛时间为0的任务都在某条关键路径上。
  4. 该算法只适用于DAG（无循环依赖），否则项目无法完成。

总结
关键路径算法通过拓扑排序和动态规划思想，计算项目的最短完成时间和关键任务。核心在于最早开始时间（正向计算）和最晚开始时间（反向计算）的差值（松弛时间）是否为0。任何关键任务的延迟都会导致项目延期，因此项目管理中需重点关注这些任务。

关键路径算法（Critical Path Method） 题目描述 在项目管理、任务调度等领域，我们常面对一个由一系列任务（或活动）构成的项目。每个任务有其预估完成所需时间（持续时间）。任务之间存在依赖关系，即某些任务必须在其他任务完成后才能开始。整个项目必须等所有任务都完成后才算结束。我们可以用一个 有向无环图 （DAG）来建模： 每个顶点表示一个任务（或事件）。 每条有向边 \(u \to v\) 表示任务 \(u\) 完成后才能开始任务 \(v\)。 每条边（或任务顶点）可以关联一个权重，表示该任务的持续时间。 我们的目标是： 计算整个项目的 最短完成时间 （即从项目开始到结束的最长路径长度，因为所有前置任务必须完成）。 识别哪些任务是 关键任务 （critical activities）—— 即其任何延迟都会直接导致整个项目延期。 计算每个任务的 最早开始时间、最晚开始时间、最早完成时间、最晚完成时间 以及 松弛时间 （slack，即可延迟的时间而不影响项目完成）。 这就是 关键路径算法 （Critical Path Method, CPM）要解决的问题。 解题过程循序渐进讲解 步骤1：图的建模 为了统一处理，我们通常对DAG做以下转换： 引入一个虚拟的 起点 （source）和 终点 （sink）。起点表示项目开始，它连接到所有没有前置任务的任务；所有没有后续任务的任务连接到终点。 将任务持续时间放在顶点上（顶点表示任务），或者放在边上（边表示任务，顶点表示事件）。这里采用“顶点表示任务”的方式更直观。 边只表示依赖关系，没有权重（或权重为0）。 例如，假设有任务A（持续3天）、B（持续2天）、C（持续4天）。依赖关系：A和B可同时开始，C必须在A和B都完成后才能开始。则图可建模为： 起点 → A → C → 终点 起点 → B → C → 终点 其中A、B、C顶点的权重是各自的持续时间。 步骤2：计算最早开始时间（Earliest Start Time, ES） 定义：ES[ v ] 表示任务v可以开始的最早时间（从项目开始时刻0起算）。 计算方法：对整个DAG进行 拓扑排序 ，然后按拓扑序递推。 对于起点（虚拟源点），ES[ source ] = 0。 对于其他顶点v，考虑所有直接前驱u，则v必须等所有前驱u完成后才能开始。 即 ES[ v] = max_ {u→v存在} (ES[ u] + duration[ u])，其中duration[ u ]是任务u的持续时间。 这是因为v必须等其所有前驱任务都完成才能开始，所以取最大值。 例子 ： 任务A（3天）、B（2天）、C（4天）、D（5天）。依赖：A→C, A→D, B→D。起点S，终点T。 拓扑序假设为 S, A, B, C, D, T。 ES[ S ] = 0 A的前驱只有S：ES[ A ] = 0 + 0 = 0 B的前驱只有S：ES[ B ] = 0 + 0 = 0 C的前驱是A：ES[ C] = ES[ A ] + 3 = 3 D的前驱是A和B：ES[ D] = max(ES[ A]+3, ES[ B ]+2) = max(3,2) = 3 T的前驱是C和D：ES[ T] = max(ES[ C]+4, ES[ D ]+5) = max(7,8) = 8 因此项目最短完成时间 = ES[ T ] = 8 天。 步骤3：计算最晚开始时间（Latest Start Time, LS） 定义：LS[ v ] 表示任务v在不推迟项目完成时间的前提下，最晚必须开始的时间。 计算方法：在拓扑排序逆序（从终点向起点）递推。 首先，设项目完成时间为 ES[ T]，令 LS[ T] = ES[ T ]（终点最晚开始等于最早开始）。 对于其他顶点v，考虑其所有直接后继w，则v必须在不影响任何后继w的最晚开始前提下完成。 即 LS[ v] = min_ {v→w存在} (LS[ w] - duration[ v ])。 接上例 ： 已知 duration[ A ]=3, B=2, C=4, D=5。 LS[ T] = ES[ T ] = 8 T的前驱是C和D： LS[ D] = LS[ T] - duration[ D ] = 8 - 5 = 3 LS[ C] = LS[ T] - duration[ C ] = 8 - 4 = 4 D的前驱是A和B： LS[ A ] 要考虑A的后继C和D： 从C看：LS[ A] ≤ LS[ C] - duration[ A ] = 4 - 3 = 1 从D看：LS[ A] ≤ LS[ D] - duration[ A ] = 3 - 3 = 0 取 min(1,0) = 0 LS[ B] 只需考虑后继D：LS[ B] = LS[ D] - duration[ B ] = 3 - 2 = 1 B的前驱是S：LS[ S ] 考虑后继A和B： 从A看：LS[ S] ≤ LS[ A] - duration[ S ] = 0 - 0 = 0 从B看：LS[ S] ≤ LS[ B] - duration[ S ] = 1 - 0 = 1 取 min(0,1) = 0 步骤4：计算松弛时间（Slack / Float） 松弛时间 = LS[ v] - ES[ v ]。 它表示任务v可以延迟多少时间开始，而不影响整个项目的最早完成时间。 如果松弛时间为0，则该任务为 关键任务 （critical activity）。 所有关键任务构成一条（或多条）从起点到终点的路径，称为 关键路径 （Critical Path）。 上例 ： S: slack = 0-0=0（虚拟起点） A: slack = 0-0=0 → 关键 B: slack = 1-0=1 → 非关键 C: slack = 4-3=1 → 非关键 D: slack = 3-3=0 → 关键 T: slack = 8-8=0（虚拟终点） 因此关键路径是 S → A → D → T，总时长 3+5 = 8 天。 步骤5：算法复杂度 拓扑排序 O(V+E)。 正向递推 ES：O(V+E)。 反向递推 LS：O(V+E)。 总体 O(V+E)，对稀疏图非常高效。 步骤6：实际应用注意事项 如果有多个起点或多个终点，添加虚拟源汇点。 如果存在“零持续时间”的依赖（仅表示顺序），可将其作为持续时间为0的任务，或直接用边表示。 关键路径可能有多条，所有松弛时间为0的任务都在某条关键路径上。 该算法只适用于DAG（无循环依赖），否则项目无法完成。 总结 关键路径算法通过拓扑排序和动态规划思想，计算项目的最短完成时间和关键任务。核心在于最早开始时间（正向计算）和最晚开始时间（反向计算）的差值（松弛时间）是否为0。任何关键任务的延迟都会导致项目延期，因此项目管理中需重点关注这些任务。