首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知有6个顶点(项点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中。 要求: 求图G的关键路径,并计算该关键路径的长度。
已知有6个顶点(项点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中。 要求: 求图G的关键路径,并计算该关键路径的长度。
admin
2015-12-30
88
问题
已知有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
学硕统考专业
相关试题推荐
关于大陆人民大规模达到台湾的第一次明确的记录出现在()。
清朝,各地督抚将重大问题径寄军机处交皇帝审批,称为()。
《关于建国以来党的若干历史问题的决议》的主要内容及其意义。
武昌起义后,全国革命形势发展的同时也潜伏着失败的危机,这主要是由于()。
《汉谟拉比法典》中规定:如果奴隶胆敢对主人说:“你不是我的主人。”他的耳朵就要被割掉。这部法典诞生于()。
美国首次提出争夺世界霸权的纲领性文件是()。
19世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
设结点x和y是二叉树中任意的两个结点,在该二叉树的先序遍历序列中x在y之前,而在其后序遍历序列中x在y之后,则x和y的关系是()。
在二叉树的顺序存储中,每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个结点,采用三叉链表存储时,每个结点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,则最后一个结点下标为k(
随机试题
中外合资经营企业和中外合作经营企业的特点不同表现在()。
继兴中会之后,资产阶级革命团体在各地陆续成立。其中,以黄兴为会长的是()
基因表达就是
患儿,5岁,近日不思饮食,嗳腐酸馊,脘腹胀满,大便酸臭,疼痛拒按,夜寐不安,手足心热,苔白厚腻,脉弦滑,治宜选用的方剂是()。
居住区内管线埋深和交叉的相互垂直净距,一般要考虑下列()因素。
能够作为抵押物的有( )。
经核准延期办理纳税申报、报送事项的,应当在纳税期内按照上期实际缴纳的税额或者税务机关核定的税额预缴税款,并在核准的延期内办理税款结算。()(2014年)
下图为世界某区域示意图。图中a为等温线(℃),b为洋流。据此完成下列问题。下列四幅“海洋表层水等温线(℃)与洋流示意图”中,与洋流b相符的是()。
甲向H银行贷款,以其别墅设定抵押。之后,甲在别墅院内建造了独立车库。贷款到期,甲无力偿还。H银行享有优先受偿权的财产:
•Youwillhearfiveshortrecordings.•Foreachrecording,decidewhatthespeaker’sstrategyisforsuccessinmanagement.•
最新回复
(
0
)