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

2024-08-23 07:17:00

题目如下图：

注：将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>

最新文章

热门文章