$v_{e_1} = 0$ ：对于源点，该事件的最早发生时间肯定事从零时刻开始，因此其最早发生时间为: $v_{e_1} = 0$ ；
$v_{e_2} = Max\{v_{e_1} + a_1\}$ ：对于顶点2，该事件要想发生，就一定得等活动 $a_1$ 结束后，而 $a_1 = 3$ ，因此，该顶点事件的最早发生时间为: $v_{e_2} = Max\{0 + 3\} = 3$ ；
$v_{e_3} = Max\{v_{e_1} + a_2\}$ ：对于顶点3，该事件要想发生，就一定得等活动 $a_2$ 结束后，而 $a_2 = 2$ ，因此，该顶点事件的最早发生时间为: $v_{e_3} = Max\{0 + 2\} = 2$ ；
$v_{e_4} = Max\{v_{e_2} + a_3, v_{e_3} + a_5\}$ ：对于顶点4，该事件要想发生，就一定得等活动 $a_3$ 与活动 $a_5$ 均结束后才能发生，而 $a_3 = 2, a_5 = 4$ ，因此，该顶点事件的最早发生时间为： $v_{e_4} = Max\{3 + 2, 2 + 4\} = Max\{5, 6\} = 6$ ；
$v_{e_5} = Max\{v_{e_2} + a_4\}$ ：对于顶点5，该事件要想发生，就一定得等活动 $a_4$ 结束后，而 $a_4 = 3$ ，因此，该顶点事件的最早发生时间为： $v_{e_5} = Max\{3 + 3\} = 6$
$v_{e_6} = Max\{v_{e_5} + a_8, v_{e_4} + a_7, v_{e_3} + a_6\}$ ：对于顶点6，该事件要想发生，就一定得等活动 $a_6, a_7, a_8$ 均结束后才能发生，而 $a_6 = 3, a_7 = 2, a_8 = 1$ ，因此，该顶点事件的最早发生时间为： $v_{e_6} = Max\{6 + 1, 6 + 2, 2 + 3\} = Max\{7, 8, 5\} = 8$

第二步：从汇点出发，令 $v_l$ (汇点) = $v_e$ (汇点)，按逆拓扑有序求其余顶点的最迟发生时间 $v_l()$

按照逆拓扑排序规则，我们许可得到其中一个逆拓扑排序序列为：

$v_6, v_5, v_4, v_3, v_2, v_1$

按照该顺序，我们依次对各个顶点的最迟发生时间进行求解：

$v_{l_6} = v_{e_6}$ ：对于汇点，我们假设该事件的最迟发生时间与最早发生时间一致，那么其对应的最迟发生时间则为： $v_6 = 8$
$v_{l_5} = Min\{v_{l_6} - a_8\}$ ：对于顶点5，在他开始后，要想让顶点6的事件准时开始，那么他就一定要给活动 $a_8$ 留出足够的时间，而 $a_8 = 1$ ，因此，顶点5的最迟发生时间为： $v_{l_5} = Min\{8 - 1\} = 7$
$v_{l_4} = Min\{v_{l_6} - a_7\}$ ：对于顶点4，在他开始后，要想让顶点6的事件准时开始，那么他就一定要给活动 $a_7$ 留出足够的时间，而 $a_7 = 2$ ，因此，顶点4的最迟发生时间为： $v_{l_4} = Min\{8 - 2\} = 6$
$v_{l_3} = Min\{v_{l_6} - a_6, v_{l_4} - a_5\}$ ：对于顶点3，在他开始后，要想让顶点6与顶点4的事件准时开始，那么他就一定要给活动 $a_6，a_5$ 留出足够的时间，而 $a_6 = 3, a_5 = 4$ ，因此，顶点3的最迟发生时间为： $v_{l_3} = Min\{8 - 3, 6 - 4\} = 2$
$v_{l_2} = Min\{v_{l_5} - a_4, v_{l_4} - a_2\}$ ：对于顶点2，在他开始后，要想让顶点5与顶点4的事件准时开始，那么他就一定要给活动 $a_4，a_3$ 留出足够的时间，而 $a_4 = 3, a_3 = 2$ ，因此，顶点2的最迟发生时间为： $v_{l_2} = Min\{7 - 3, 6 - 2\} = 4$
$v_{l_1} = Min\{v_{l_2} - a_1, v_{l_3} - a_2\}$ ：对于顶点1，在他开始后，要想让顶点2与顶点3的事件准时开始，那么他就一定要给活动 $a_1，a_2$ 留出足够的时间，而 $a_1 = 3, a_2 = 2$ ，因此，顶点1的最迟发生时间为： $v_{l_3} = Min\{4 - 3, 2 - 2\} = 0$

现在我们就得到了各个顶点的最早开始时间与最迟开始时间，如下所示：

	v₁	v₂	v₃	v₄	v₅	v₆
最早开始时间v_e	0	3	2	6	6	8
最迟开始时间v_l	0	4	2	6	7	8

第三步：根据各顶点的 $v_e()$ 值求所有弧的最早开始时间 $e ()$

按照前面我们求出的各顶点的最早开始时间，我们就行求得各弧的最早开始时间：

弧 $v_1, v_2>$ ：其表示的活动为 $a_1$ ，因此其最早开始时间为： $e_1 = v_{e_1} = 0$
弧 $v_1, v_3>$ ：其表示的活动为 $a_2$ ，因此其最早开始时间为： $e_2 = v_{e_1} = 0$
弧 $v_2, v_4>$ ：其表示的活动为 $a_3$ ，因此其最早开始时间为： $e_3 = v_{e_2} = 3$
弧 $v_2, v_5>$ ：其表示的活动为 $a_4$ ，因此其最早开始时间为： $e_4 = v_{e_2} = 3$
弧 $v_3, v_4>$ ：其表示的活动为 $a_5$ ，因此其最早开始时间为： $e_5 = v_{e_3} = 2$
弧 $v_3, v_6>$ ：其表示的活动为 $a_6$ ，因此其最早开始时间为： $e_6 = v_{e_3} = 2$
弧 $v_4, v_6>$ ：其表示的活动为 $a_7$ ，因此其最早开始时间为： $e_7 = v_{e_4} = 6$
弧 $v_5, v_6>$ ：其表示的活动为 $a_8$ ，因此其最早开始时间为： $e_8 = v_{e_5} = 6$

第四步：根据各顶点的 $v_l()$ 值求所有弧的最迟开始时间 $l ()$

同理，我们也可以求得各弧的最迟开始时间：

弧 $v_1, v_2>$ ：其表示的活动为 $a_1$ ，因此其最迟开始时间为： $l_1 = v_{l_2} - a_1= 4 - 3 = 1$
弧 $v_1, v_3>$ ：其表示的活动为 $a_2$ ，因此其最迟开始时间为： $l_2 = v_{l_3} - a_2 = 2 - 2 = 0$
弧 $v_2, v_4>$ ：其表示的活动为 $a_3$ ，因此其最迟开始时间为： $l_3 = v_{l_4} - a_3= 6 - 2 = 4$
弧 $v_2, v_5>$ ：其表示的活动为 $a_4$ ，因此其最迟开始时间为： $l_4 = v_{l_5} - a_4 = 7 - 3 = 4$
弧 $v_3, v_4>$ ：其表示的活动为 $a_5$ ，因此其最迟开始时间为： $l_5 = v_{l_4} - a_5 = 6 - 4 = 2$
弧 $v_3, v_6>$ ：其表示的活动为 $a_6$ ，因此其最迟开始时间为： $l_6 = v_{l_6} - a_6 = 8 - 3 = 5$
弧 $v_4, v_6>$ ：其表示的活动为 $a_7$ ，因此其最迟开始时间为： $l_7 = v_{l_6} - a_7 = 8 - 2 = 6$
弧 $v_5, v_6>$ ：其表示的活动为 $a_8$ ，因此其最迟开始时间为： $l_8 = v_{l_6} - a_8 = 8 - 1 = 7$

现在我们就得到了所有弧的最早开始时间与最迟开始时间，如下所示：

	a₁	a₂	a₃	a₄	a₅	a₆	a₇	a₈
最早开始时间e	0	0	3	3	2	2	6	6
最迟开始时间l	1	0	4	4	2	5	6	7

第五步：求 $A OE$ 网中所有活动的差额 $d ()$ ，找出所有 $d () = 0$ 的活动构成关键路径

根据求得的各弧的最早开始时间与最迟开始时间，我们便可以求得各活动的二者时间差额，如下所示：

	a₁	a₃	a₄	a₅	a₆	a₇	a₈
最迟开始时间l	1	4	4	2	5	6	7
最早开始时间e	0	3	3	2	2	6	6
时间差额d	1	1	1	0	3	0	1

根据差额大家可以找到关键活动： $a_2, a_5, a_7$ ，而这些活动所对应的关键路径为：

2.3 关键活动与关键路径的特性

在一项工程中，关键路径与关键活动具有一下特性：

若关键活动的时间增加，则整个工程的工期将会延长
若关键活动的时间在一定范围内缩短，则整个工程的工期会被缩短
若关键活动的时间缩短超过这一范围，则该关键路径会转为非关键路径，其对应的活动也会变为非关键活动。
若 AOE网中的关键路径并不唯一，当网中存在多条关键路径时，只提高一条关键路径上的关键活动速度，并不能缩短整个工程的工期；只有加快那些包括所有关键路径上的关键活动，才能达到缩减工期的目的

以吃苹果这个工程来理解这些特性：就是下面我们还

在这个工程中，两条路径：

路径1

路径2

均为该工程的关键路径，其中活动 $a_4$ 为两条路径共有的关键活动，那么当大家缩短该工程的时间时，整个工程的工期都会缩短；

当我们缩短活动 $a_1$ 或者活动 $a_3$ 的时间时，此时路径1不再是关键路径，其路径上的活动也不再是关键活动，因此，其时间变化并不会影响整个工程的工期；

当我们增加某个活动的时间是，整个工程的工期将被延长，且不包含该活动的路径变为非关键路径；

在上图中，关键路径为：

工程的工期为： $5 + 3 + 5 = 13$

当大家缩短关键路径上的活动 $a_1, a_3$ 的总时间时间在 $\sim 2$ 这个范围内时，整个工程的工期将被缩短
当超过该范围时，该路径将变为非关键路径，路径上的活动 $a_1, a_3$ 将变为非关键活动

结语

今天的内容到这里就全部结束了，通过今天的学习，我们框架掌握了图论中极具实用价值的关键路径分析方法。让我们来详细回顾本文的核心知识点：

AOE网的核心概念
- 顶点表示事件，有向边表示活动，边权值表示活动开销
- 与AOV网的区别：AOV网顶点表示活动，AOE网边表示活动
- 两个重要性质：事件触发活动的开始，活动完成触发事件的发生
- 仅有一个源点（入度为0）和一个汇点（出度为0）
关键路径的核心定义
- 从源点到汇点的最长路径决定了整个工程的最短工期
- 关键路径上的活动称为关键活动，其延迟会直接影响总工期
- 工程最短做完时间 = 关键路径的长度
五大关键参数体系
- 事件最早发生时间ve(k)：ve(k) = Max{ve(j) + Weight(vj, vk)}
- 事件最迟发生时间vl(k)：vl(k) = Min{vl(j) - Weight(vk, vj)}
- 活动最早开始时间e(i)：e(i) = ve(k)（活动起点的最早发生时间）
- 活动最迟开始时间l(i)：l(i) = vl(j) - Weight(vk, vj)
- 时间余量d(i)：d(i) = l(i) - e(i)，d(i)=0的活动为关键活动
关键路径五步算法：
1. 拓扑排序求所有事件的最早发生时间ve()
2. 逆拓扑排序求所有事件的最迟发生时间vl()
3. 根据ve()求所有活动的最早开始时间e()
4. 根据vl()求所有活动的最迟开始时间l()
5. 计算时间余量d()，d(i)=0的活动构成关键路径
关键路径的重要特性
- 关键活动时间增加 → 总工期延长
- 关键活动适度缩短 → 总工期缩短
- 关键活动过度缩短 → 可能转为非关键活动
- 多关键路径时需同时优化所有路径上的关键活动