关键路径

AOE 网

对于一个带权的有向无环图，用顶点表示事件，边表示活动，权代表活动持续时间的网络称为边活动网（Activity On Edge Network, AOE 网）。

AOE 网的特点

1. 表示实际工程计划的 AOE 网应该是无回路的。
2. 只有一个入度为零的顶点（称作源点），表示整个活动开始。
3. 只有一个出度为零的顶点（称作汇点），表示整个活动结束。

关键路径与关键活动

在 AOE 网中，路径长度最长的路径称为关键路径（Critical Path），关键路径上的活动都叫做关键活动（Critical Activity）。

• 关键路径的实际含义是：整个工程所需要的最短时间。
• 关键活动的实际含义是：将关键活动的权值增加，会使得有向图上的最长路径长度增加，即会使得最短工期增加。

事件最早发生时间与最迟发生时间

简单来说，事件最早发生时间就是最早某个事件只能在什么时间开始，如果开始更早那么其前置要求不会被满足。事件最迟发生时间是指某个事件最迟是什么时间开始，如果开始时间更迟那么会影响整体进度。

最早发生时间是受到源点的最大距离影响的，最迟时间是受到汇点的最小距离影响的。

事件最早发生时间 $ve(i)$

$ve(i)$ 是从源点 $v_i$ 到 $v_j$ 的最长路径长度。这个长度决定了所有从顶点 $v_j$ 发出的活动能够开工的最早时间。

• $ve(0)=0$
• $ve(j)=\max \{ve(i)+\text{len}(v_i,v_j)\}$，其中 $(v_i,v_j)\in E$

事件最迟发生时间 $vl(i)$

$vl(i)$ 是指在不推迟整个工期的前提下，事件 $v_i$ 允许的最晚发生时间。

• 如果 $v_i$ 是汇点，$vl(i)=ve(i)$
• 如果 $v_i$ 不是汇点，$vl(i)=\min \{vl(j)-\text{len}(v_i,v_j)\}$，其中 $(v_i,v_j)\in E$

假设汇点为 $v_n$，从后往回计算（从汇点开始计算），$vl(i)=ve(n)-\text{len}(v_i,v_n)$。

活动最早开始时间与最晚开始时间

活动最早开始时间 $e[i]$

若活动 $a_i$ 是由弧 $(v_j,v_k)$ 表示，则活动 $a_i$ 的最早开始时间应等于事件 $v_j$ 的最早发生时间。因此有：

$$e[i]=ve[j]$$

活动最晚开始时间 $l[i]$

若活动 $a_i$ 由弧 $(v_j,v_k)$ 表示，则 $a_i$ 的最晚开始时间要保证事件 $v_k$ 的最迟时间不拖后。因此：

$$l[i]=vl[k]-\text{len}(v_j,v_k)$$

关键活动的判定

算出所有活动的最早与最晚开始时间后，最早开始时间等于最晚开始时间的活动为关键活动，由此也可以找到关键路径。

链接到

• 上一个知识点：7.9 拓扑排序
• 下一个知识点：7.11 Dijkstra算法