关键路径法

关键路径法（critical path method，CPM）用任务先后网络计算项目的最早完成时间、每项活动可推迟的余量，以及决定工期的最长依赖链。经典CPM假定工期确定、任务开始无额外资源竞争，活动只有“前项完成后才能开始”的先后条件。人员不足或机器冲突会使实际排程晚于此下界。

项目有五项活动：A三天、B两天、C两天、D一天、E一天；A结束才能做C，B结束才能做D，C与D都完成后才能做E。A—C—E需六天，B—D—E只需四天；E不能因为D已结束就提前开始，必须等较慢的C。

最早时刻的正向递推

将活动作为顶点、依赖作为有向边。网络必须为有向无环图；存在正工期依赖环时，所有先后不等式相加即矛盾。记 $E{S}_i$ 为最早开始、$E{F}_i=E{S}_i+p_i$ 为最早完成，则 $$E{S}_i=max(\{E{F}_j:j\to i\}\cup \{0\}).$$ 按拓扑序计算，前驱已经全部确定。任意可行安排都不能早于全部前驱的结束，因此递推给出下界；每项恰在该时刻开始又满足全部先后关系，所以同时达到这个界。

主例A、B最早从零开始，C从三到五，D从二到三，E从五到六。最早工期 $T=\underset{i}{max}E{F}_i=6$。在每个合流点取“最大”，正是最长路径而非最短路径的原因。

箭头是依赖，不按工期比例计长度。E有两个前驱，开始时间由较晚完成的C决定。

最晚时刻与总浮时

固定不晚于 $T$ 完工，令 $L{F}_i$ 为最晚完成、$L{S}_i=L{F}_i-p_i$ 为最晚开始。逆拓扑计算： $$L{F}_i=min(\{L{S}_k:i\to k\}\cup \{T\text{若无后继}\}).$$ 有后继时取它们最晚开始的最小值；没有后继才取项目截止时间。否则某个后继就会被延误。反向归纳既证明这些限制必要，也说明在最晚时刻开工可满足依赖和截止要求。

主例各活动的 $(ES,EF,LS,LF)$ 为A $(0,3,0,3)$，B $(0,2,2,4)$，C $(3,5,3,5)$，D $(2,3,4,5)$，E $(5,6,5,6)$。总浮时为 $T{F}_i=L{S}_i-E{S}_i$，A、C、E为零，B、D为二。B和D各有两天总浮时不表示两项可在最早方案上各自独立再推迟两天而无视先后关系；浮时须沿同一网络协调使用。

可复算实现

输入非负有限工期和先后边，输出工期、每项的四时刻和总浮时。程序用拓扑扫描拒绝循环，不依赖编号已经按先后排列。

Python 3

from collections import deque
import math

def critical_path(duration, edges):
    p, edges = tuple(duration), tuple(edges)
    n = len(p)
    if any(not math.isfinite(v) or v < 0 for v in p):
        raise ValueError("finite nonnegative durations required")
    successor, predecessor = [[] for _ in p], [[] for _ in p]
    for a,b in edges:
        if type(a) is not int or type(b) is not int or not (0 <= a < n and 0 <= b < n):
            raise ValueError("invalid edge")
        successor[a].append(b); predecessor[b].append(a)
    indegree = [len(v) for v in predecessor]
    queue = deque(i for i,d in enumerate(indegree) if d == 0)
    es, order = [0]*n, []
    while queue:
        a = queue.popleft(); order.append(a)
        for b in successor[a]:
            es[b] = max(es[b], es[a]+p[a])
            indegree[b] -= 1
            if indegree[b] == 0:
                queue.append(b)
    if len(order) != n:
        raise ValueError("cyclic dependency graph")
    ef = [es[i]+p[i] for i in range(n)]
    total = max(ef,default=0)
    lf, ls = [total]*n, [0]*n
    for i in reversed(order):
        if successor[i]:
            lf[i] = min(ls[j] for j in successor[i])
        ls[i] = lf[i]-p[i]
    return total, [(es[i],ef[i],ls[i],lf[i],ls[i]-es[i]) for i in range(n)]

print(critical_path([3,2,2,1,1], [(0,2),(1,3),(2,4),(3,4)]))
# (6, [(0,3,0,3,0), (0,2,2,4,2), (3,5,3,5,0),
#      (2,3,4,5,2), (5,6,5,6,0)])

每条边在正向与反向各处理常数次，时间与空间均为 $O(n+|E|)$。零工期虚活动可以使用，但即使循环全部为零，代码也会按DAG约定拒绝。浮点工期产生的接近零浮时需要合理容差；本例整数运算可精确核对。

变式。 将B工期从二改为四，两条链都变成六天，出现两条关键路径，B、D也变为零浮时。因此只把某条原关键路径缩短，不保证整体项目同样缩短。资源受限项目调度还要在这个依赖下界上加入逐时资源约束；不确定工期可进一步参考计划评审技术。