求关键路径

基本概念

AOE 网中，每个节点称为一个事件，其中有两个比较特殊的点

各节点之间弧的权重 w 表示一个活动 ai 的持续时间，每个事件有最早开始时间 ve 和最晚开始时间 vl，每个活动也有最早开始时间 e 和最晚开始时间 l。其中 l=e 的活动所组成的路径称为关键路径。关键路径中包含的活动称为关键活动

事件的最早开始时间 ve
从源点开始，源点的最早开始时间为 0，其后的事件依次为前一个节点的最早开始时间加上对应弧的权重。如果某一个节点有多个入度，则该事件的最早开始时间取各个入度计算结果中的最大值。

事件的最晚开始时间 vl
最晚开始时间需要从汇点开始推，汇点的最晚开始时间等于其最早开始时间，接下来依次向前推，每个顶点的最晚开始时间等于后一个顶点的最晚开始时间减去对应弧的权重。如果该点有多个出度，则该事件的最晚开始时间取各个出度计算结果中的最小值。

活动的最早开始时间 e
一个活动的最早开始时间等于该活动所对应的弧的弧尾的最早开始时间。

活动的最晚开始时间 l
活动的最晚开始时间等于该活动所对应弧的弧头的最晚开始时间减去该弧的权重。

下面是一个实际的例子：

Imgur

事件对应的最早开始时间的推算

v1 为源点，故 v1 的最早开始时间是 0
v2 的入度为 1，它的最早开始时间等于 v1 的最早开始时间加上连接它们之间弧的权重 a1，结果是 0+3=3
v3 的入度为 1，它的最早开始时间等于 v1 的最早开始时间加上连接它们之间弧的权重 a2，结果是 0+2=2
v4 的入度为 2，首先计算出对应的两个时间，
1. v2 的最早开始时间加上它们之间弧的权重 a3，结果是 3+2=5
2. v3 的最早开始时间加上它们之间弧的权重 a5，结果是 2+4=6
3. 比较上面的两个结果 6>5，故 v4 的最早开始时间是 6
v5 的入度为 1，它的最早开始时间等于 v2 的最早开始时间加上连接它们之间弧的权重 a4,结果是 3+3=6
v6 的入度为 3,首先计算出对应的三个时间：
1. v3 的最早开始时间加上它们之间弧的权重 a6，结果是 2+3=5
2. v4 的最早开始时间加上它们之间弧的权重 a7，结果是 6+2=8
3. v5 的最早开始时间加上它们之间弧的权重 a8，结果是 6+1=7
4. 比较三个结果 8>7>5，故 v6 的最早开始时间是 8

事件对应的最晚开始时间的推算

v6 为汇点，v6 的最晚开始时间等于其最早开始时间等于 8
v5 的出度为 1, 它的最晚开始时间等于 v6 的最晚开始时间减去它们之间弧的权重 a8, 结果是 8-1=7
v4 的出度为 1, 它的最晚开始时间等于 v6 的最晚开始时间减去它们之间弧的权重 a7, 结果是 8-2=6
v3 的出度为 2,首先计算对应的两个时间：
1. v6 的最晚开始时间减去它们之间弧的权重 a6, 结果是 8-3=5
2. v4 的最晚开始时间减去它们之间弧的权重 a5, 结果是 6-4=2
3. 比较上面的两个值 2<5，故 v3 的最晚开始时间是 2
v2 的出度为 2，首先计算对应的两个时间：
1. v5 的最晚开始时间减去它们之间弧的权重 a4, 结果是 7-3=4
2. v4 的最晚开始时间减去它们之间弧的权重 a3, 结果是 6-2=4
3. 比较上面的两个结果 4=4,故 v3 的最晚开始时间为 4
v1 的出度为 2，首先计算对应的两个时间：
1. v2 的最晚开始时间减去它们之间弧的权重 a1, 结果是 4-3=1
2. v3 的最晚开始时间减去它们之间弧的权重 a2, 结果是 2-2=0
3. 比较上面的两个结果 0<1,故 v3 的最晚开始时间为 0

活动对应的最早开始时间的推算

活动所对应的最早开始时间等于活动所对应弧的弧尾的最早开始时间，所以

e(a1)=ve(v1)=0
e(a2)=ve(v1)=0
e(a3)=ve(v2)=3
e(a4)=ve(v2)=3
…

活动对应的最晚开始时间的推算

活动所对应的最晚开始时间等于活动所对应弧的弧头的最晚开始时间减去活动的持续时间（即该弧的权重），所以：

l(a1)=el(v2)-a1=4-3=1
l(a2)=el(v3)-a2=2-2=0
l(a3)=el(v4)-a3=6-2=4
l(a4)=el(v5)-a4=7-3=4
…

关键路径的确定

找出活动时间表当中 l=e 的活动 a2,a5,a7 即是关键路径中对应的关键活动，由这些关键活动构成的关键路径如下图：

Imgur