数据结构 图-关键路径：AOE网络

AOE定义

在带权有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销（如完成活动所需的时间），即用边表示活动的网络称为AOE网络。 注： AOE网络一定是有向无环图。

活动发生时间计算

首先明确事件最早发生时间，记为Ve(i)，就是一个人从源点沿着箭头走到该顶点所花费的最长时间。例如：走到V2花费3天，而从V1走到V4有2条路，v1->v2->v4 这条路花费的是3+2天，而v1->v3->v4花费的是2+4天，选择出花费时间最多的路径。这样依次计算出到每个顶点花费的时间。如下表所示：

事件最迟发生时间：，记为Vl(i).注意这里有一个很重要的前提：保证时间不推迟的前提下（就是这个人走到V6的时间和上面的V(6)时间必须相同）。不明白可以通过下面例子找出规律。 如首先在上表中找到v6的值，如下：

接着计算顶点V5，V5 = V6 - v5的权值 ：8 - 1 = 7 ，填入表中：

接着计算V4 = V6 - V4的权值 ：8 - 2 = 6，填入表中：

接着计算V3，注意V3指向V4和V6，V3与V6：V6- V3权值：8-3=5 而V6与V4: V4 - V3权值： 6-4=2，取出V3的最小值 2 填入表中：

依照上面的规律完成关键活动表如下：

各活动计算

对题目中的活动进行一个编号 e(i)：活动a(i)的最早开始时间，如活动a1可以写成弧<v1,v2>那么a1的活动为弧头V1的ve(1)即e(1) = ve(1)= 0（v(1)见下表）

同理可以依次完成各个弧的e(i)表：

l(i)：活动a(i)的最迟开始时间，如活动a1可以写成弧<v1,v2>即V1指向V2，那么根据下表l(1) = vl(2)- 3(a1弧的权值)= 1,即当前活动的弧尾顶点vl(i)-权值。

根据上面的规律可以完成活动表:

关键活动计算

上面计算出活动表，根据活动表筛选出关键活动，条件就是e(i)=l(i)，如下：

筛选出的关键活动就是: a2, a5, a7 关键路径 v1,v3,v4,v6

总结

1. 计算 ve：找到达该顶点路径的最大权值和
2. 计算vl: 利用ve表倒序求各个顶点：所求的顶点被指向的顶点减去权值（若结果有多个值取最小值）
3. 计算a(i)：a(i)等于当前弧的弧头ve
4. 计算l(i) : e(i)等于当前弧的弧尾vl - 权值
5. 令l(i) = a(i),找到关键活动
6. 连接关键活动找到关键路径