关键路径

关键路径研究的是：在一个具有先后依赖关系的工程中，哪些活动决定了整个工程最早能在什么时候完成。

一个工程由许多活动组成，部分活动必须等前面的活动完成后才能开始。从工程起点到终点，耗时最长的依赖路径就是关键路径。

AOE 网的基础概念

什么是 AOE 网

关键路径建立在 AOE 网（Activity On Edge Network，边表示活动的网络）之上。

图中元素	表示的含义
顶点	事件，表示某些活动已经完成，可以进入下一阶段
有向边	活动
边的权值	完成该活动所需的时间

AOE 网中的活动与事件满足：

1. 只有顶点所代表的事件发生后，从该顶点出发的各项活动才能开始。
2. 只有进入某顶点的所有边所代表的活动都已完成，该顶点所代表的事件才能发生。

例如：

       3
  v1 -----> v2
   \         |
  5 \        | 4
     \       v
      -----> v3 -----> v4
                  2

边 v1 → v2 的权值为 3，表示该活动需要 3 个时间单位。

开始顶点与终点

• 开始顶点（源点）： 入度为 0 的顶点，表示整个工程的起点。
• 终点（汇点）： 出度为 0 的顶点，表示整个工程的终点。

AOE 网通常只有一个开始顶点和一个终点。若原图存在多个源点或汇点，可以根据需要增加虚拟源点或虚拟汇点，使工程具有统一的起点和终点。

源点 v1 ──→ …… ──→ 汇点 vn

AOE 网必须是有向无环图

AOE 网本质上是一个有向无环图（DAG）。如果图中存在环，例如：

A → B → C
↑       ↓
└───────┘

就会形成“A 完成后才能做 B，B 完成后才能做 C，C 完成后又才能做 A”的循环依赖，导致工程无法启动。

重点：AOE 网必须是 DAG，这也是关键路径算法需要使用拓扑排序的根本原因。

关键路径的含义

为什么要求关键路径

假设一个项目有两条并行的任务链：

开始
 ├─ A：3 天 ─ B：5 天 ─┐
 │                     ├─ 完成
 └─ C：4 天 ─ D：2 天 ─┘

两条路径所需时间分别为：

A → B：3 + 5 = 8 天
C → D：4 + 2 = 6 天

整个工程不能在第 6 天结束，因为第一条路径尚未完成。因此工程最早需要 8 天完成，A → B 就是决定总工期的关键路径。

• 关键路径上的活动如果延误，整个工程通常也会延误。
• 非关键路径上的活动可能允许在一定范围内推迟。

关键路径的本质

在 AOE 网中，从源点到汇点的最长路径就是关键路径，关键路径上的活动称为关键活动。

最短路径关心“从一个顶点到另一个顶点最快怎么走”，关键路径关心“整个工程至少需要多久才能全部完成”。因为所有必要活动都完成后工程才能结束，所以总工期由耗时最长的依赖链决定：

$$\boxed{\text{工程的最短完成时间}=\text{关键路径的长度}}$$

五个关键参数

设事件为 $v_k$，活动为 $a_i$。寻找关键活动时需要计算以下五个参数：

符号	对象	含义
$v_e(k)$	事件 $v_k$	最早发生时间
$v_l(k)$	事件 $v_k$	最迟发生时间
$e(i)$	活动 $a_i$	最早开始时间
$l(i)$	活动 $a_i$	最迟开始时间
$d(i)$	活动 $a_i$	时间余量，即 $l(i)-e(i)$

计算时先求事件的 $v_e(k)$ 和 $v_l(k)$，再由它们求活动的 $e(i)$、$l(i)$ 和 $d(i)$。

事件的发生时间

事件 $v_k$ 的最早发生时间 $v_e(k)$

$v_e(k)$ 是从源点 $v_1$ 到顶点 $v_k$ 的最长路径长度。它决定了所有从 $v_k$ 出发的活动最早能在什么时候开始。

初始化源点：

$$v_e(\text{源点})=0.$$

若 $v_k$ 有多个直接前驱 $v_j$，则必须等待所有前驱活动完成，因此取最大值：

$$\boxed{ v_e(k)= \max_{\langle v_j,v_k\rangle} \left\{v_e(j)+\operatorname{Weight}(v_j,v_k)\right\} }.$$

其中，$\operatorname{Weight}(v_j,v_k)$ 表示有向边 $\langle v_j,v_k\rangle$ 的权值。

例如，若源点 $v_1$ 在第 0 时刻发生，且有 v1 --3--> v2，则 $v_e(1)=0$、$v_e(2)=3$。

在拓扑排序中计算 $v_e$

$v_e$ 可以在拓扑排序过程中同步计算：

1. 初始化所有顶点的最早发生时间：$v_e[1\ldots n]=0$。

2. 每当输出一个入度为 0 的顶点 $v_j$，就检查它的所有直接后继 $v_k$。

3. 若

   $$v_e[j]+\operatorname{Weight}(v_j,v_k)>v_e[k],$$

   则更新

   $$v_e[k]=v_e[j]+\operatorname{Weight}(v_j,v_k).$$

4. 重复以上过程，直到输出全部顶点。

求 $v_e$：按拓扑序从前往后，对所有前驱取最大值。

事件 $v_k$ 的最迟发生时间 $v_l(k)$

$v_l(k)$ 表示在不推迟整个工程完成时间的前提下，事件 $v_k$ 最晚必须发生的时间。

先用工程总工期初始化汇点：

$$v_l(\text{汇点})=v_e(\text{汇点}).$$

若 $v_k$ 有多个直接后继 $v_j$，为了保证所有后继事件都不晚于各自的最迟发生时间，需要取最小值：

$$\boxed{ v_l(k)= \min_{\langle v_k,v_j\rangle} \left\{v_l(j)-\operatorname{Weight}(v_k,v_j)\right\} }.$$

例如，若有 v2 --3--> v3，并且 $v_l(3)=10$，则

$$v_l(2)=10-3=7.$$

按逆拓扑序计算 $v_l$

计算 $v_l$ 时需要使用逆拓扑序：

1. 在拓扑排序时用栈记录顶点的输出顺序，排序结束后依次出栈，即可得到逆拓扑序。

2. 若汇点为 $v_n$，初始化所有顶点：$v_l[1\ldots n]=v_e[n]$。

3. 每次弹出顶点 $v_j$，检查它的所有直接前驱 $v_k$。

4. 若

   $$v_l[j]-\operatorname{Weight}(v_k,v_j)<v_l[k],$$

   则更新

   $$v_l[k]=v_l[j]-\operatorname{Weight}(v_k,v_j).$$

5. 重复以上过程，直到栈空。

求 $v_l$：按逆拓扑序从后往前，对所有后继取最小值。

两种事件时间的计算方向

• 计算 $v_e(k)$ 前，需要先知道所有前驱事件的最早发生时间，所以使用拓扑序。
• 计算 $v_l(k)$ 前，需要先知道所有后继事件的最迟发生时间，所以使用逆拓扑序。

时间	计算方向	取值规则
$v_e$	拓扑序，从前向后	对所有前驱取最大值
$v_l$	逆拓扑序，从后向前	对所有后继取最小值

活动的开始时间

若边 $\langle v_k,v_j\rangle$ 表示活动 $a_i$，则该活动的持续时间为 $\operatorname{Weight}(v_k,v_j)$。

活动 $a_i$ 的最早开始时间 $e(i)$

活动要等其起点事件发生后才能开始，因此

$$\boxed{e(i)=v_e(k)}.$$

例如，若 $v_e(k)=5$，则从 $v_k$ 出发的活动 $a_i$ 最早在第 5 时刻开始。

活动 $a_i$ 的最迟开始时间 $l(i)$

活动必须在终点事件最迟发生之前完成，因此

$$\boxed{l(i)=v_l(j)-\operatorname{Weight}(v_k,v_j)}.$$

例如，活动 v2 --3--> v3 中，若 $v_l(3)=10$，则

$$l(i)=10-3=7.$$

也就是说，该活动最迟必须在第 7 时刻开始。

时间余量与关键活动

活动 $a_i$ 的最迟开始时间与最早开始时间之差称为时间余量：

$$\boxed{d(i)=l(i)-e(i)}.$$

它表示在不延长整个工程总工期的前提下，活动 $a_i$ 可以拖延的时间。

例如，若 $e(i)=3$、$l(i)=5$，则 $d(i)=2$，说明该活动可以推迟 2 个时间单位而不影响总工期。

如果

$$\boxed{d(i)=0},$$

即 $l(i)=e(i)$，说明活动 $a_i$ 必须如期完成，否则会导致整个工程延误。这样的活动称为关键活动。

求关键路径的算法步骤

按照教材中的顺序，求关键路径可分为以下五步：

1. 从源点出发，令 $v_e(\text{源点})=0$，按拓扑有序序列求其余顶点的最早发生时间 $v_e(k)$。
2. 从汇点出发，令 $v_l(\text{汇点})=v_e(\text{汇点})$，按逆拓扑有序序列求其余顶点的最迟发生时间 $v_l(k)$。
3. 根据各顶点的 $v_e(k)$，求所有活动的最早开始时间 $e(i)$。
4. 根据各顶点的 $v_l(k)$，求所有活动的最迟开始时间 $l(i)$。
5. 计算 AOE 网中所有活动的时间余量 $d(i)=l(i)-e(i)$，由所有满足 $d(i)=0$ 的关键活动构成关键路径。

按拓扑序计算 v_e
        ↓
按逆拓扑序计算 v_l
        ↓
计算每项活动的 e、l
        ↓
计算 d = l - e
        ↓
找出 d = 0 的关键活动
        ↓
得到关键路径

确定关键路径

从源点到汇点，把关键活动连续连接起来，形成的完整路径就是关键路径（Critical Path）。

v1 --a1--> v2 --a2--> v4
 \                       ^
  \--a3--> v3 --a4-------|

若 $a_1$、$a_2$ 是关键活动，而 $a_3$、$a_4$ 不是，则 v1 → v2 → v4 是关键路径。

关键路径可能不止一条

如果有多条从源点到汇点的路径长度都等于网络中的最大路径长度，那么它们都是关键路径。例如：

A 路径：3 + 4 = 7
B 路径：2 + 5 = 7

此时两条路径都是关键路径。若存在多条关键路径，只缩短某一条路径上的单个关键活动，不一定能缩短总工期，因为其他关键路径仍可能保持原来的长度。

公式速记

$$\boxed{ v_e(k)= \max_{\langle v_j,v_k\rangle} \left\{v_e(j)+\operatorname{Weight}(v_j,v_k)\right\} }$$ $$\boxed{ v_l(k)= \min_{\langle v_k,v_j\rangle} \left\{v_l(j)-\operatorname{Weight}(v_k,v_j)\right\} }$$ $$\boxed{ e(i)=v_e(k), \qquad l(i)=v_l(j)-\operatorname{Weight}(v_k,v_j) }$$ $$\boxed{d(i)=l(i)-e(i)}$$ $$\boxed{d(i)=0\Longleftrightarrow a_i\text{ 是关键活动}}$$

核心记忆：$v_e$ 按拓扑序取最大，$v_l$ 按逆拓扑序取最小；先求事件时间，再求活动时间，最后用 $d(i)=0$ 找关键活动。

---

吼吼吼，
今天的任务终于结束了。
明天是周六，可以美美睡懒觉了。
最近这几天学习任务有点紧张，放松下🥰。