首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知有6个顶点(项点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。 要求： 求图G的关键路径，并计算该关键路径的长度。
已知有6个顶点(项点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。 要求： 求图G的关键路径，并计算该关键路径的长度。
admin
2015-12-30
60
问题
已知有6个顶点(项点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。
要求：
求图G的关键路径，并计算该关键路径的长度。
选项
答案
按照算法，先计算各个事件的最早发生时间，计算过程如下： ve(0)=0； ve(1)=ve(0)+a
0→1
=4； ve(2)=max{ve(0))+a
0→1
，ve(1)+a
1→2
}=max(6，4+5)=9； ve(3)=ve(2)+a
2→3
=9+4=13； ve(4)=ve(2)+a
2→4
=9+3=12； ve(5)=max{ve(3)+a
3→5
，ve(4)+a
4→5
}=max(16，15：)=16； 接下来求各个时间的最迟发生时间，计算过程如下： vl(5)=ve(5)=16； vl(4)=vl(5)-a
4→5
=16-3=13； vl(3)=vl(5)-a
3→5
=16-3=13； vl(2)=min{vl(3)-a
2→3
，vl(4)-a
2→4
}=min(9，10)=9； vl(1)=vl(2)-a
1→2
=4； v1(0)=min{vl(2)-a
0→2
，Vl(1)-a
0→1
}=min(3，0)； 即ve()和vl()数组如下表所示： [*] 接下来计算所有活动的最早和最迟发生时间e()和l()： e(a
0→1
)=e(a
0→2
)=ve(0)=0； e(a
1→2
)ve(1)=4； e(a
2→3
)=e(a
2→4
)=ve(2)=9； e(a
3→5
)-ve(3)=13； e(a
4→5
)=ve(4)=12； l(a
4→5
)=vl(5)-a
4→5
=16-3=13； l(a
3→5
)=vl(5)-a
3→5
=16-3=13； l(a
2→4
)=vl(4)a
2→4
=13-3=10； l(a
2→3
)-vl(3)-a=
2→3
13-4=9； l(a
1→2
)=vl(2)-a
1→2
=9-5=4： l(a
0→2
)=vl(2)-a
0→2
=9-6=3； l(a
0→1
)=vl(1)-a
0→1
=4-4=0； e()和l()数组与它们的差值如下表所示： [*] 满足l()-e()=0的路径就是关键路径，所以关键路径为a
0-＞1
、a
1-＞2
、a
2-＞3
、a
3-＞5
，如下图所示(粗线表示)。 [*]
解析
转载请注明原文地址:https://kaotiyun.com/show/EBRi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列关于基督教的叙述，不正确的是()。
洋务运动中翻译出《几何原本》后九卷、《代数学》、《重学》等数学、物理方面的科技书籍的翻译家是()。
我国对外开放格局的形成过程。
美国主张建立国际联盟的主要目的是()。
洋务派创办军事工业的方式是()。
明朝灭亡后，以下南明小朝廷存在的先后顺序是()。①绍武政权②永历政权③隆武政权④弘光政权
(1)所有事件的最早发生时间如下：Ve(1)=0Ve(2)==5Ve(3)=6Ve(4)=max{ve(2)+3，ve(3)+6}=12Ve(5)=max{ve(3)+3，ve(4)+3}=15Ve(6)=ve(4)+4=16Ve(7)=ve
关于死锁的银行家算法是围绕“安全状态”的概念工作的。当系统预测到不安全状态时，就拒绝分配资源，但是，银行家算法要求的条件并不是必要的。例如，某系统有12个资源供进程P0、P1、P2使用。目前的分配情况如下：(1)请说明系统处于不安全状态；(2
执行一次磁盘输入输出操作所花费的时间包括()。
如果I／O设备与存储设备间的数据交换不经过CPU来完成，则这种数据交换方式是()。
随机试题
假设“记事本”已经打开并且正在编辑一个文档，想再打开一个文档而不关闭当前文档，可以采用的方法是。
患者，女，38岁。乳癌根治术并化疗。出院时对预防复发最重要的指导是
某女，67岁。症见精神萎顿，倦怠乏力，自汗，易于感冒，舌淡，脉虚。其病机是
权益净利率在杜邦分析体系中是个综合性最强，最具有代表性的指标。通过对系统的分析可知,提高权益净利率的途径不包括()。
笑冰心雨声渐渐地住了，窗帘后隐隐地透进清光来。推开窗户一看，呀!凉云散了，树叶上的残滴，映着月儿，好似萤光千点，闪闪烁烁地动着。——真没想到苦雨孤灯之后，会有这么一幅清关的图画!凭
下列广告语中不科学的是：
简述当前我国中小学德育中存在的主要问题。
若函数f调用了函数g，函数g又调用了函数f，则以下说法中正确的是()。
Atsometimeinyourlifeyoumayhaveastrongdesiretodosomethingstrangeorterrible.【R1】______Youknowthattocommitthe
Themainideaofthetextisthat______.Asuitabletitleforthistextis______.
最新回复
(
0
)
