数据结构 图之关键路径

如题所述

第1个回答  2022-07-07

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

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

下表为各顶点(事件)的ve值:

下表为各顶点(事件)的vl值:

e(i):活动ai是由弧<vk,vj>表示,则活动的最早开始时间应该和事件vk的最早发生时间相等,因此,就有e(i)=ve(k)。即: 边(活动)的最早开始时间等于它发出的顶点(事件)的的最早发生时间

参考之前的个顶点的ve和c:

得出的e(i)值:

l(i):活动ai是由弧<vk,vj>表示,则ai的最晚发生时间要保证vj的最迟发生时间不拖后(vj最迟发生时间为9的话,ai的最迟时间就必须是 9-活动耗时 )。因此,l(i)=vl(i)-len<vk,vj>,即:活动到达顶点的最晚发生时间减去边的权重

参考之前的个顶点的ve和c:

l(i) = 当前边的指向结点的最晚发生时间[vl(i)] - 当前时间(即边)所消耗的时间

列出总表:

其中 e(i)==l(i)的边 :

a1 a2 a4 a8 a9

所组成的路径即为关键路径 :

a1->a4->a9 和 a2->a8->a9

相似回答