数据结构期末复习( はち)--VOA图关键路径求法

题目如下图:

注:将123456当成abcdef.

事件最早发生事件求法:找从原点到该事件的最长路径(从前往后推)

        对a:Ve=0    

        对b:Ve=max{ 2 , 15+4 }=19

        对c:Ve=15

        对d:Ve=19+10=29

        对e:   Ve=max{ 19+19,15=17 }=38        对f:Ve=38+5=43

事件最晚发生时间求法:找从终点到该事件的最长路径,再做减法(从后往前推) 

    对f:Vl=43

         对e:   Vl=43-5=38

         对d:Vl=43-4=39

         对c:Vl=min{ 43-(10+6+4), 43-(5+19+4), 43-(5+11) }=15

        对b:Vl=min{ 43-(10+6) , 43-(19+5) }=19

        对a:Vl=0 

活动(弧)的最早开始时间求法:取决于活动头端点的事件发生的最早时间

        对ab:E=Ve(a)=0        对ac:E=Ve(a)=0

        对be:E=Ve(b)=19     对bd:  E=Ve(b)=19

        对cb:   E=Ve(c)=15     对ce:   E=Ve(c)=15

        对df:E=Ve(d)=29     对ef:    E=Ve(e)=38

活动(弧)的最晚开始时间求法:取决于尾端的Vl,再减去弧的权值 

        对ab:L=Vl(b)-2=17        对ac:L=Vl(c)-15=0

        其他类似

综上所述,可得下表:

    

事件 a b c d e f
Ve 0 19 15 29 38 43
Vl 0 19 15 37 38 43
活动 ab ac cb bd be ce df ef
权值 2 15 4 10 19 11 6 5
e 0 0 15 19 19 15 29 38
l 17 0 15 27 19 27 37

38

关键路径即e与l相等的路径:<a,c>,<c,b>,<b,e>,<e,f>

原文地址:https://www.cnblogs.com/DSYR/p/9217126.html