1.AOE网
在带权图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销。
1.2 性质
- 只有在某顶点所代表的时间发生后，从该顶点出发的各有向边所代表的活动才能开始；
- 只有在进入某顶点的各有向边所代表的活动已结束时，该顶点所代表的事件才能发生；
- 有些活动可以并行执行。
1.3 相关概念
- 在AOE网中，仅有一个入度为0的顶点，称为开始顶点（源点），它表示整个工程的开始。
- 也仅有一个出度为0的顶点，称为结束顶点（汇点），它表示整个工程的结束；
- 从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动；
- 完成整个工程的最短时间就是关键路径的长度，若关键路径不能按时完成，则整个工程的完成时间就会延长。
2.关键路径求解方式
2.1 最早发生时间
2.1.1 事件Vk最早发生时间Ve(k)
决定了所有从Vk开始的活动能够开工的最早时间
- 按照拓扑排序的顺序，依次求各个顶点事件的Ve(k)
Ve(源点) = 0Ve(k) =Max{ve(j) + Weight(vj, Vk)}，Vj为Vk的任意前驱
2.1.2 活动ai的最早时间e(i)
指该活动弧的起点所表示的事件的最早发生事件
- 若弧<vk, vj>表示活动ai，则有
e(i) = Ve(k)
2.1.3 示例
计算上图Ve(k)和e(i)
| A | B | C | D | E | F | G | H | J | |
| Ve(k) | 0 | 6 | 4 | 5 | 8 | 7 | 17 | 15 | 26 |
| a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 | a9 | a10 | a11 | a12 | |
| e(i) | 0 | 0 | 0 | 6 | 4 | 5 | 5 | 8 | 8 | 7 | 15 | 17 |
2.2 最迟发生时间
2.2.1 事件Vk的最迟发生事件Vl(k)
指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间
- 按逆拓扑排序序列，依次求各个顶点的Vl(k)
- Vl(汇点) = Ve(汇点)
Vl(k) =Min{Vl(j) - Weight(vk, vj)}，Vj为Vk的任意后继
2.2.2 活动ai的最迟发生事件l(i)
指该活动弧的终点所表示事件的最迟发生事件与该活动所需时间之差
- 若边<vk, vj>表示活动ai，则有
l(i) = Vl(j) - Weight(Vk, Vj)
2.2.3 示例
计算上图Vl(k)和l(i)
Vl(E) = Min{24-9, 15 -7} = 8
Vl(D) = Min{7-2, 8-3} = 5
Vl(A) = Min{7-6, 7-4, 5-5} = 0
| A | B | C | D | E | F | G | H | J | |
| Vl(k) | 0 | 7 | 7 | 5 | 8 | 7 | 24 | 15 | 26 |
| a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 | a9 | a10 | a11 | a12 | |
| l(i) | 1 | 3 | 0 | 7 | 7 | 5 | 5 | 15 | 8 | 7 | 15 | 24 |
2.3 活动ai的时间余量d(i)
在不增加完成整个工程所需总时间的情况下，活动ai可以拖延的时间
若一个活动的时间余量为零，则该活动时关键活动，由关键活动可得关键路径。
d(i) = l(i) - e(i)
2.3.1 示例
| A | B | C | D | E | F | G | H | J | |
| Ve(k) | 0 | 6 | 4 | 5 | 8 | 7 | 17 | 15 | 26 |
| Vl(k) | 0 | 7 | 7 | 5 | 8 | 7 | 24 | 15 | 26 |
| a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 | a9 | a10 | a11 | a12 | |
| e(i) | 0 | 0 | 0 | 6 | 4 | 5 | 5 | 8 | 8 | 7 | 15 | 17 |
| l(i) | 1 | 3 | 0 | 7 | 7 | 5 | 5 | 15 | 8 | 7 | 15 | 24 |
| d(i) | 1 | 3 | 0 | 1 | 3 | 0 | 0 | 7 | 0 | 0 | 0 | 7 |
由上图，构成两条关键路径：
- A → D → E → H → J
- A → D → F → H → J
3.关键路径特性
- 若关键活动耗时增加，则整个工程的工期将增长
- 缩短关键活动的时间，可以缩短整个工程的工期
- 当缩短到一定程度时，关键活动路径可能变成非关键活动
- 可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。