【数据结构】关键路径

1. AOE网

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称AOE网（Activity On Edge NetWork）。

AOE网具有以下两个性质：

1. 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
2. 只有在进入某顶点的各有向边所代表的活动都结束时，该顶点所代表的事件才能发生；
3. 有些活动是可以并行进行的。

AOE网中仅有一个入度为0的顶点，称为开始顶点（源点），它表示整个工程的开始。也仅有一个出度为0的顶点，称为结束顶点（汇点），它表示整个工程的结束。

2. 关键路径

从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。

完成整个工程的最短时间就是关键路径的程度，若关键活动不能按时完成，则整个工程的完成时间就会延长。

事件vk的最早发生时间ve(k)——决定了所有从vk开始的活动能够开工的最早时间。

活动ai的最早开始时间e(i)——指该活动弧的起点所表示的事件的最早发生时间。

事件vk的最迟发生时间vl(k)——它是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间。

活动ai的最迟开始时间l(i)——它是指该活动弧的终点所表示的事件最迟发生的时间与该活动所需时间之差。

活动ai的时间余量d(i)=l(i)-e(i)，表示在不增加完成整个工程所需时间的情况下，活动ai可以拖延的时间。若一个活动的时间余量为零，则说明该活动必须要如期完成，d(i)=0即l(i)=e(i)的活动ai是关键活动，由关键活动组成的路径就是关键路径。

3. 求关键路径的步骤

1. 求所有事件的最早发生时间ve()
2. 求所有事件的最迟发生时间vl()
3. 求所有活动的最早发生时间e()
4. 求所有活动的最迟发生时间l()
5. 求所有活动的时间余量d()

d(i)=0的活动就是关键活动，由关键活动可得关键路径。

1. 求所有事件的最早发生时间ve()

按拓扑排序序列，依次求各顶点的ve(k):

ve（源点）=0

ve(k)=Max{ve(j)+Weight(vj,vk)}，vj为vk的任意前驱。

拓扑排序序列：V1、V3、V2、V5、V4、V6

2. 求所有事件的最迟发生时间vl()

按逆拓扑排序序列，依次求各个顶点的vl(k)。

vl（汇点）=ve（汇点）

vl(k)=Min{vl(j)-Weight(vk,vj)}，vj为vk的任意后继。

逆拓扑排序序列为：V6、V5、V4、V2、V3、V1

3. 求所有活动的最早发生时间e()

若边<vk,vj>表示活动ai，则有e(i)=ve(k)。

4. 求所有活动的最迟发生时间l()

若边<vk,vj>表示活动ai，则有l(i)=vl(j)-Weight(vk,vj)

5. 求所有活动的时间余量d()

d(i)=l(i)-e(i)

说明：d(k)=0的活动就是关键活动，由关键活动可得关键路径。

关键活动：a2、a5、a7

关键路径：V1 -> V3 -> V4 -> V6

4. 关键活动、关键路径特性

若关键活动耗时增加，则整个工程的工期将增长。

缩短关键活动的时间，可以缩短整个工程的工期。

当缩短到一定程度时，关键活动可能会变成非关键活动。

一个工程可能有多条关键路径，只提高一条关键路径上的关键活动并不能缩短整个工程工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的，例如：a4=2（炒菜）缩短。

5. 小结