关键路径计算器

伪代码

按拓扑序对活动网络做两趟扫描：正向求每项任务最早可能发生的时刻，反向求在不推迟项目的前提下它最晚可以发生的时刻。

CPM(活动集, 依赖集):
    顺序 = 拓扑排序(活动集)

    // 正向扫描：最早开始与最早结束
    对 顺序 中的每项活动 a:
        ES[a] = max(EF[p]，p 为 a 的前驱)，否则为 0
        EF[a] = ES[a] + 工期[a]
    T = max(EF[a]，遍历所有 a)      // 项目总工期

    // 反向扫描：最晚开始与最晚结束
    对 逆序(顺序) 中的每项活动 a:
        LF[a] = min(LS[s]，s 为 a 的后继)，否则为 T
        LS[a] = LF[a] - 工期[a]

    时差[a] = LS[a] - ES[a]
    关键路径 = 时差为 0 的活动

关键路径是网络中最长的那条路径而不是最短的，这使它成为 DAG 上的最大化问题，而不是最短路径问题。由于网络无环，这两趟扫描不过是按拓扑序进行的动态规划，完全不需要优先队列。时差为零意味着该活动没有任何回旋余地：把它推迟一天，整个项目就顺延一天。

分步示例演算

为一个四活动项目排期，其中两项任务可以并行，但都必须完成之后第三项才能开始。

示例图: 活动及工期为 A（3 天）、B（2 天）、C（4 天）和 D（2 天）。依赖关系：A 与 B 都必须先于 C，C 又先于 D。

1. 正向扫描，A 与 B. 两者都没有前驱，因此都在时刻 0 开始。A 在 3 结束，B 在 2 结束。它们并行进行。
2. 正向扫描，C. C 要等两者都完成，因此它的最早开始是 3 与 2 中的较大者，也就是 3。它历时 4 天，在 7 结束。请注意 B 早一天完成，只能干等着。
3. 正向扫描，D. D 在 7 开始，在 9 结束。它之后没有别的活动，因此项目总工期为 9 天。
4. 反向扫描. 从 9 往回推：D 最晚必须在 7 开始，因此 C 必须在 7 结束、在 3 开始。于是 A 与 B 都必须在 3 之前完成，这使 A 的最晚开始为 0，B 的最晚开始为 1。
5. 计算时差. A 的最晚开始 0 减最早开始 0，时差为 0。B 的最晚开始 1 减最早开始 0，时差为 1。C 与 D 的时差都是 0。

项目历时 9 天，关键路径是 A 到 C 到 D。B 拥有一天的机动，也就是说它可以晚一天开始或者超期一天而不影响完工日期。这正是它的实用价值：它明确告诉管理者应当把注意力放在哪里。压缩 B 毫无意义，而压缩 A、C 或 D 中的任何一项都能缩短整个项目，至少在关键路径转移到经由 B 之前是如此。

复杂度及其来源

时间: O(V + E) · 空间: O(V)

一次拓扑排序的代价是 O(V + E)，而两趟扫描各自访问每项活动一次、每条依赖边一次，因此也都是 O(V + E)。空间是每项活动四个数字，即最早与最晚的开始和结束，也就是 O(V)。整个方法是线性的，因此它能扩展到包含数十万项活动的项目网络。依赖网络必须是有向无环图：循环依赖不存在拓扑序，相应地也就没有任何合法排期，因此环检测是一项真正的前置条件而非形式。

何时使用关键路径法 (CPM)，何时不宜

CPM 假定工期已知且资源无限。放松其中任何一条假设，问题就变了。

常见陷阱

• 正向扫描中取最小值而不是最大值. 一项活动必须等到所有前驱都完成才能开始，因此最早开始时刻是前驱结束时刻的最大值。取最小值会得到一个短得不可能实现、而且悄无声息就是错的排期。
• 以为关键路径唯一. 可能有多条路径并列为最长，此时它们上面的每一项活动时差都是零。只压缩其中一条毫无用处，因为另一条关键路径仍然决定着完工日期。
• 忘记关键路径会转移. 把某个关键活动压缩得足够多，另一条路径就会变成最长。压缩必须在每次改动之后重新评估，而不能依据最初那一次分析一次性全部实施。
• 忽视资源上限. CPM 假定 A 与 B 确实可以同时进行。如果两者需要同一台机器或同一个人，这份排期就是虚构的，此时需要的是 RCPSP。
• 在含环的网络上运行它. 循环依赖意味着不存在拓扑序，也就没有任何合法排期。请检测出这个环并报告出来，而不是从一个部分顺序里硬生生算出一堆数字。

常见问题

什么是关键路径法？

CPM 在由活动和依赖构成的网络中找出最长路径，这条路径决定了项目可能的最短工期。位于该路径上的活动时差为零，因此其中任何延误都会推迟整个项目。它通过一趟正向扫描求最早时刻、一趟反向扫描求最晚时刻来计算。

CPM 中的时差是什么？

时差是一项活动可以推迟而不影响项目完工日期的时间量，计算方式是最晚开始减去最早开始。时差为零的活动就是关键活动。在上面的例子中，活动 B 有一天时差，而 A、C、D 都没有。

关键路径法的时间复杂度是多少？

O(V + E)，其中 V 是活动数，E 是依赖数。它是一次拓扑排序外加两趟对网络的线性扫描，因此能轻松扩展到非常庞大的项目计划。

CPM 与 PERT 有什么区别？

CPM 为每项活动使用单一的确定性工期，重点在于找出关键路径和时差。PERT 为每项活动使用三个估计值，即乐观、最可能与悲观，从而算出期望工期和方差，据此可以说出在给定日期完工的概率。两者的网络分析本身完全相同。

项目进行过程中关键路径会变吗？

会，而且这是最主要的实务陷阱。如果某个关键活动被压缩，或者某个非关键活动吃掉了自己的时差，另一条路径就可能变成最长的。这项分析应当随着实际工期逐渐明朗而重新进行，而不能当作规划时就已经定死。