数据结构图关键路径
AOV网络：有向图，用顶点表示活动，用弧表示活动的先后顺序
AOE网络：有向图，用顶点表示事件，用弧表示活动，用权值表示活动消耗时间
名词解释
活动：业务逻辑中的行为，用边表示
事件：活动的结果或者触发条件
关键路径：具有最大路径长度（权重）的路径，可能不止一条
活动的两个属性：e(i)最早开始时间，l(i)最晚开始时间
事件的两个属性：ve(j)最早开始时间，vl(j)最晚开始时间
在下面的计算过程中，就可以理解这些属性的概念了
计算关键路径的过程
原理：
- 先求出每个顶点的ve和vl值
- 通过这两个值就可以求出每条边的e和l值。
- 取e(i)=l(i)的边就是
关键路径上的边，关键路径不止一条
一、求ve(j)的值
- 从前向后，直接前驱节点的ve值＋当前节点的边的权值（有可能多条，取最大值）
- 第一个顶点的ve等于0
下表为各顶点（事件）的ve值：
| 顶点 | v1 | v2 | v3 | v4 | v5 | v6 | v7 |
|---|---|---|---|---|---|---|---|
| ve(j) | 0 | 3 | 2 | 6 | 7 | 5 | 10 |
二、求vl(j)的值
- 从后向前，直接后继节点的vl值－当前节点的边的权值（有可能多条，取最小值）
- 终结点的vl等于它的ve
| 顶点 | v1 | v2 | v3 | v4 | v5 | v6 | v7 |
|---|---|---|---|---|---|---|---|
| vl(j) | 0 | 3 | 3 | 6 | 7 | 6 | 10 |
三、求e(i)的值
e(i):活动ai是由弧<vk,vj>表示，则活动的最早开始时间应该和事件vk的最早发生时间相等，因此，就有e(i)=ve(k)。即：边（活动）的最早开始时间等于它发出的顶点(事件)的的最早发生时间
| 边 | a1(3) | a2(6) | a3(2) | a4(4) | a5(2) | a6(1) | a7(3) | a8(1) | a9(3) | a10(4) |
|---|---|---|---|---|---|---|---|---|---|---|
| e(i) | 0 | 0 | 0 | 3 | 3 | 2 | 2 | 6 | 7 | 5 |
四、求l(i)的值
l(i):活动ai是由弧<vk,vj>表示，则ai的最晚发生时间要保证vj的最迟发生时间不拖后（vj最迟发生时间为9的话，ai的最迟时间就必须是 9-活动耗时 ）。因此，l(i)=vl(i)-len<vk,vj>，即：活动到达顶点的最晚发生时间减去边的权重
| 边 | a1(3) | a2(6) | a3(2) | a4(4) | a5(2) | a6(1) | a7(3) | a8(1) | a9(3) | a10(4) |
|---|---|---|---|---|---|---|---|---|---|---|
| l(i) | 0 | 0 | 1 | 3 | 4 | 5 | 3 | 6 | 7 | 6 |
五、求出关键边和关键路径
e(i)==l(i)的边：
a1 a2 a4 a8 a9
关键路径：
a1->a4->a9 和 a2->a8->a9
