首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
已知有6个顶点(项点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。 要求： 求图G的关键路径，并计算该关键路径的长度。
已知有6个顶点(项点编号为0～5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。 要求： 求图G的关键路径，并计算该关键路径的长度。
admin
2015-12-30
111
问题
已知有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://www.kaotiyun.com/show/EBRi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列历史事件发生的先后顺序是()①“铁幕”演说②马歇尔计划③北大西洋公约
1941年8月14日，罗斯福和丘吉尔发表了()，表示了反对纳粹暴政的决心，这是反法西斯同盟建立过程中的重要一环。
以下不是巴黎和会的主要议题的是()
第三世界所共有的特征及崛起的标志是什么?
商代青铜器的制作技术很高，尤其是礼器的制作，造型美观，纹饰精巧，是水平极高的工艺品，其中主流的花纹是()。
某激光打印机每分钟打印20页，每页4000字符，相应的设备驱动程序一次输出一个字符，采用中断方式，CPU处理每次中断需50微秒，则CPU用于打印的开销是()。
一组记录的关键字为{25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是()。
某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生产者提供的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区的速度快，则缓冲区个数的最优值应为()。
指令系统字长16位，每个地址码为6位，采用扩展操作码的方式，试设计14条二地址指令，100条一地址指令，100条零地址指令。(1)画出操作码的扩展形式。(2)下图为指令译码逻辑图，其中只给出了二地址指令的译码逻辑，试补全一地址指令和零地址指令的
试述分页存储管理的基本实现原理，并说明如何实现从逻辑空间到物理空间的变换?
随机试题
增值税一般纳税人兼营不同增值税税率的货物或增值税应税劳务，未分别核算或不能准确核算其销售额的，其增值税税率适用的确定方法是_________。
A．行气豁痰B．补气，回阳，醒神C．开窍，活血，顺气，降逆D．开窍，顺气，解郁气厥实证治法宜首选
患者因情志不遂，出现失眠健忘，坐卧不宁，抑郁不乐，渐致神志痴呆，反应迟钝，喃喃自语，问之不答，舌质淡红，苔白腻，脉弦滑，最佳治法为（ ）。
( )原则指在保证完成组织目标的前提下，在管理组织的结构、各层次的职能分工、权力和专业的结合、操作层的专门化几个部门的管理跨度等方面实现最优和组织运行费用最低。
某企业拥有期限为一年的商业汇票,本金是100万元,日息为10‰,截止评估日离付款期尚差6个月的时间,由此确定评估值为()。
税务代理执业人员可以以个人名义直接接受涉税专业服务业务的委托。()
依法落实旅游市场监管责任，强化政府的领导责任。在地方层面，地方各级人民政府建立健全旅游综合协调、旅游案件联合查办、()等综合监管机制，统筹旅游市场秩序整治工作。
2，2，6，12，27，( )
AGermanlawrequiringsocialmediacompanieslikeFacebookandTwittertoquicklyremovehatespeechfromtheirsitesissetto
Accordingtosomedoctorsandpoliticians,theamountofsaltconsumed______.Thephrase"vocal...exponent"(line2,para.5)mo
最新回复
(
0
)
