首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知有6个顶点(项点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中。 要求: 求图G的关键路径,并计算该关键路径的长度。
已知有6个顶点(项点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中。 要求: 求图G的关键路径,并计算该关键路径的长度。
admin
2015-12-30
91
问题
已知有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
学硕统考专业
相关试题推荐
洋务运动中翻译出《几何原本》后九卷、《代数学》、《重学》等数学、物理方面的科技书籍的翻译家是()。
论述斯巴达的阶级结构、政治制度和社会风尚
1923年纳粹党魁希特勒发动了“啤酒馆暴动”,对此叙述不正确的一项是()。
下列标志着周王室在春秋时代的地位一落千丈,仅存虚名的选项是()
文艺复兴运动兴起的时间是()。
下列哪个文件标志着“文化大革命”的发起?()
《凡尔赛条约》中,战胜国以()方式处置德国的全部海外殖民地。
“二战”期间,美国研制了原子弹并用于实践;1946年美国投入使用的第一台电子计算机最初是用于计算炮弹弹道的;德国人研制成功的远程液体火箭是用于空袭英国的。以上史实说明()。
程序员利用系统调用打开I/O设备时,通常使用的设备标识是____。
某数码相机内置128MB的存储空间,拍摄分辨率设定为1600×1200像素,颜色深度为24位,若不采用压缩存储技术,使用内部存储器最多可以存储的照片数是()。
随机试题
DNA分子上能被RNA聚合酶特异结合的部位叫作()
口有涩味如食生柿子的感觉属于
半夏除燥湿化痰,降逆止呕外,还有的功效是
根据商品房建设的需要,可以依照法律程序提前收回已出让的土地使用权,但在收回时应根据土地使用者利用土地的实际情况和土地的剩余年限给予适当赔偿。()
在工程经济分析中,以投资收益率指标作为主要决策依据,其可靠性较差的原因在于()。
根据《会计档案管理办法》的规定,会计档案的保管期限为永久定期两类。会计档案的定期保管期限最短为()
对于《普通高中语文课程标准(实验)》中提出的“表达与交流”方面的实施建议,下列理解不正确的是()。
为了解幼儿同伴交往特点,研究者深入幼儿所在的班级,详细记录其交往过程的语言和作等。这一研究方法属于()。
科学的可靠性还源于科学界具有公认的评价准则,所以能对理论取得一致意见,因此在比较成熟的科学领域,一个问题无论问哪一个科学家,都可以得到大致相同的答案。哲学、伦理学等学科没有公认的评价准则,同一个问题问不同的哲学家或伦理学家可能得到完全相反的结果,令人无所适
Foxesandfarmershavenevergotonwell.Thesesmalldog-likeanimalshavelongbeenaccusedofkillingfarmanimals.Theyare
最新回复
(
0
)