首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知有6个顶点(项点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中。 要求: 求图G的关键路径,并计算该关键路径的长度。
已知有6个顶点(项点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中。 要求: 求图G的关键路径,并计算该关键路径的长度。
admin
2015-12-30
89
问题
已知有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
学硕统考专业
相关试题推荐
以下选项中中原王朝对西藏管辖设置机构对应有误的一项是()。
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
1945年,联合国成立之时,创始会员国共有()个国家。
第三世界所共有的特征及崛起的标志是什么?
十字军东征的目标是解放圣地()。
“一战”后,协约国与奥地利签订的确认奥匈帝国解体的文件是()。
在4×100米接力赛中,4个运动员之间存在如下关系:运动员1跑到终点把接力棒交给运动员2;运动员2一开始处于等待状态,在接到运动员1传来的接力棒后才能往前跑,他跑完100米后交棒给运动员3;运动员3也只有接到运动员2传来的接力棒后才能往前跑,他跑完100米
以数组Data[m+1]作为循环队列SQ的存储空间,front为头指针,rear为队尾指针,则执行出队操作的语句是()。
以下关于图的说法正确的是()。.I在一个有向图的拓扑序列中,若顶点a在顶点b之前,则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O,则该图的拓扑序列必定存在Ⅲ在.AOE网中一定只有一条
设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态,且进程A先得到CPU运行,进程B后运行。进程A的运行轨迹为:计算50ms,打印信息100ms,再计算50ms,打印信息100ms,结束。进程B的运行轨迹为:计算50ms,输
随机试题
切开法重睑术若损伤上睑提肌腱膜会出现以下哪种情况
可用于治疗急性肺水肿的药物是长期应用可诱发痛风的药物是
治疗外感表证兼有食积者,宜选用的药物是()
安全监管部门对某生产经营单位进行安全生产监督检查。根据《安全生产法》,关于对该单位安全监督检查的说法,错误的是()。
下列货物在进出境申报前,要向海关办理货物备案,完成前期相应工作的有()。
(2012年山东.47)下列有关医药常识不正确的是()。
Thereisvirtuallynolimittohowonecanservecommunityinterests,fromspendingafewhoursaweekwithsomecharitableorga
下列控件中与数据表中的字段没有关系的是()。
【B1】【B17】
A、GotoParisagain.B、LiveinParis.C、Gosomewhereelse.D、Difficulttosay.C综合推断题,男士说明年应该做点儿别的,由此可知,男士明年会去别的地方,故选C
最新回复
(
0
)