一、什么是关键路径
在带权有向图中，以 顶点 表示 事件，以 有向边 表示 活动，以边上的 权值 表示完成该活动的 开销（如完成活动所需的时间），称之为用边表示活动的网络，简称 AOE 网（Activity On Edge NetWork）.
AOE 网具有以下两个性质：
- 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
- 只有在进入某顶点的各有向边所代表的活动都已经结束时，该顶点所代表的事件才能发生，另外，有些活动是可以并时进行的；
在 AOE 网中仅有一个入度为 0 的顶点，称为 开始顶点（源点），它表示整个工程的开始；也仅有一个出度为 0 的顶点，称为 结束顶点（汇点），它表示整个工程的结束。从源点到汇点的有向路径可能存在多条，所有路径中，具有最大路径长度的路径称为 关键路径，而把关键路径上的活动称为 关键活动。完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长。
二、关键路径的相关术语
- 事件 \(v_{k}\) 的最早发生事件 ve(k)：决定了所有从 \(v_{k}\) 开始的活动能够开工的最早时间；
- 活动 \(a_{i}\) 的最早发生时间 e(i)：指该活动弧的起点所表示的事件的最早发生时间；
- 事件 \(v_{k}\) 的最迟发生时间 vl(k)：它是指不推迟整个工程完成的前提下，该事件最迟发生的时间；
- 活动 \(a_{i}\) 的最迟开始时间 l(i)：它是指该活动弧的终点所表示时间的最迟发生时间与该活动所需时间之差；
- 活动 \(a_{i}\) 的时间余量 d(i)=l(i)-e(i)：它表示在不增加完成整个活动所需总时间的情况下，活动 \(a_{i}\) 可以拖延的时间；
若关键活动耗时增加，则整个工程的工期将增加；
缩短关键活动的时间，可以缩短整个工程的工期；
当缩短到一定程度是，关键活动可能会变成非关键活动；
可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的活动才能达到缩短工期的目的；
三、求关键路径的步骤
-
求所有事件的最早发生时间 ve(k)：
- 按拓扑排序序列，依次求各个顶点 \(ve(k):\begin{cases} ve(源点) = 0 \\ ve(k) = Max\{ve(j) + Weight(v_{j},v_{k})\} & ,v_{j} 为 v_{k} 的任意前驱 \end{cases}\)
-
求所有事件的最迟发生时间 vl(k)：
- 按逆拓扑排序序列，依次求各个顶点的\(vlk(k): \begin{cases} vl(汇点) = ve(汇点) \\ vl(k) = Min\{vl(j) - Weight(v_{k},v_{j})\} & ,v_{j} 为 v_{k} 的任意后继 \end{cases}\)
-
求所有活动的最早发生时间 e(k)：
- 若边 \(<v_{k},v_{j}>\) 表示活动 \(a_{i}\)，则有 \(e(i) = ve(k)\)
-
求所有活动的最迟发生时间 l(k)：
- 若边 \(<v_{k},v_{j}>\) 表示活动 \(a_{i}\)，则有 \(l(i) = vl(j) - Weight(v_{k},v_{j})\)
-
求所有活动的是时间余量 d(k)：
- \(d(i) = l(i) - e(i)\)
| \(v_{1}\) | \(v_{2}\) | \(v_{3}\) | \(v_{4}\) | \(v_{5}\) | \(v_{6}\) | |
|---|---|---|---|---|---|---|
| ve(k) | 0 | 3 | 2 | 6 | 6 | 8 |
| vl(k) | 0 | 4 | 2 | 6 | 7 | 8 |
| \(a_{1}\) | \(a_{2}\) | \(a_{3}\) | \(a_{4}\) | \(a_{5}\) | \(a_{6}\) | \(a_{7}\) | \(a_{8}\) | |
|---|---|---|---|---|---|---|---|---|
| e(k) | 0 | 0 | 3 | 3 | 2 | 2 | 6 | 6 |
| l(k) | 1 | 0 | 4 | 4 | 2 | 5 | 6 | 7 |
| d(k) | 1 | 0 | 1 | 1 | 0 | 3 | 0 | 1 |