数据结构－图－关键路径

github地址：https://github.com/arkulo56/thought/blob/master/software/dataStruct/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E5%9B%BE_%E5%85%B3%E9%94%AE%E8%B7%AF%E5%BE%84.md

数据结构图关键路径

AOV网络：有向图，用顶点表示活动，用弧表示活动的先后顺序
AOE网络：有向图，用顶点表示事件，用弧表示活动，用权值表示活动消耗时间

名词解释

活动：业务逻辑中的行为，用边表示
事件：活动的结果或者触发条件
关键路径：具有最大路径长度（权重）的路径，可能不止一条

---

活动的两个属性：e(i)最早开始时间，l(i)最晚开始时间
事件的两个属性：ve(j)最早开始时间，vl(j)最晚开始时间

在下面的计算过程中，就可以理解这些属性的概念了

---

计算关键路径的过程

原理：

1. 先求出每个顶点的ve和vl值
2. 通过这两个值就可以求出每条边的e和l值。
3. 取e(i)=l(i)的边就是关键路径上的边，关键路径不止一条

一、求ve(j)的值

1. 从前向后，直接前驱节点的ve值＋当前节点的边的权值（有可能多条，取最大值）
2. 第一个顶点的ve等于0

下表为各顶点（事件）的ve值：

顶点	v1	v2	v3	v4	v5	v6	v7
ve(j)	0	3	2	6	7	5	10

二、求vl(j)的值

1. 从后向前，直接后继节点的vl值－当前节点的边的权值（有可能多条，取最小值）
2. 终结点的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