2. 考研
  3. 已知有6个顶点(项点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。 要求： 求图G的关键路径，并计算该关键路径的长度。

已知有6个顶点(项点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。 要求： 求图G的关键路径，并计算该关键路径的长度。

admin2015-12-30  84
问题 已知有6个顶点(项点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。

要求：
求图G的关键路径，并计算该关键路径的长度。
选项
答案按照算法，先计算各个事件的最早发生时间，计算过程如下： ve(0)=0； ve(1)=ve(0)+a0→1=4； ve(2)=max{ve(0))+a0→1，ve(1)+a1→2}=max(6，4+5)=9； ve(3)=ve(2)+a2→3=9+4=13； ve(4)=ve(2)+a2→4=9+3=12； ve(5)=max{ve(3)+a3→5，ve(4)+a4→5}=max(16，15：)=16； 接下来求各个时间的最迟发生时间，计算过程如下： vl(5)=ve(5)=16； vl(4)=vl(5)-a4→5=16-3=13； vl(3)=vl(5)-a3→5=16-3=13； vl(2)=min{vl(3)-a2→3，vl(4)-a2→4}=min(9，10)=9； vl(1)=vl(2)-a1→2=4； v1(0)=min{vl(2)-a0→2，Vl(1)-a0→1}=min(3，0)； 即ve()和vl()数组如下表所示： [*] 接下来计算所有活动的最早和最迟发生时间e()和l()： e(a0→1)=e(a0→2)=ve(0)=0； e(a1→2)ve(1)=4； e(a2→3)=e(a2→4)=ve(2)=9； e(a3→5)-ve(3)=13； e(a4→5)=ve(4)=12； l(a4→5)=vl(5)-a4→5=16-3=13； l(a3→5)=vl(5)-a3→5=16-3=13； l(a2→4)=vl(4)a2→4=13-3=10； l(a2→3)-vl(3)-a=2→313-4=9； l(a1→2)=vl(2)-a1→2=9-5=4： l(a0→2)=vl(2)-a0→2=9-6=3； l(a0→1)=vl(1)-a0→1=4-4=0； e()和l()数组与它们的差值如下表所示： [*] 满足l()-e()=0的路径就是关键路径，所以关键路径为a0-＞1、a1-＞2、a2-＞3、a3-＞5，如下图所示(粗线表示)。 [*]
解析
转载请注明原文地址:https://kaotiyun.com/show/EBRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)