首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下图中的顶点表示村庄,有向边代表交通路线,若要建立一家医院,试问建在哪一个村庄能使各村庄总体交通代价最小?
下图中的顶点表示村庄,有向边代表交通路线,若要建立一家医院,试问建在哪一个村庄能使各村庄总体交通代价最小?
admin
2012-06-26
85
问题
下图中的顶点表示村庄,有向边代表交通路线,若要建立一家医院,试问建在哪一个村庄能使各村庄总体交通代价最小?
选项
答案
该图的邻接矩阵如下: [*] 利用Floyd算法可求得两顶点之间最短路径长度。最后求得: [*] 从A
4
中可求得每对村庄之间的最少交通代价。假设医院建在i村庄时,其他各村庄往返总的交通代价如下所示: 医院建在村庄0时,各村庄往返总的交通代价为12+16+4+7+13+16+4+18=90; 医院建在村庄1时,各村庄往返总的交通代价为1 3+29+17+20+12+11+8+5=1 15。 医院建在村庄2时,各村庄往返总的交通代价为16+11+12+6+16+29+12+34=136; 医院建在村庄3时,各村庄往返总的交通代价为4+8+12+3+4+17+12+22=82; 医院建在村庄4时,各村庄往返总的交通代价为18+5+34+22+7+20+6+3=115。 显然,把医院建在村庄3时总体交通代价最少。
解析
本题主要考查Floyd算法的思想和解题步骤。Floyd算法的基本思想是:
假设求从顶点v
i
到v
j
的最短路径。如果从v
i
到v
j
有弧,则从v
i
到v
j
存在一条长度为arcs
[j]的路径,该路径不一定是最短路径,尚需进行n次试探。
(1)首先考虑路径(v
i
,v
0
,v
j
)是否存在,即判别弧(v
i
,v
0
)和(
0
,v
j
是否存在。如果存在,则比较(v
i
,v
j
)和(v
i
,v
0
,v
j
)的路径长度,取长度较短者为从v
i
到v
j
的中间顶点的序号不大于0的最短路径。
(2)假如在路径上再增加一个顶点v
1
,也就是说,如果(v
i
,……,v
1
)和(v
1
,……,v
j
)分别是当前找到的中间顶点的序号不大于0的最短路径,那么(v
i
,……,v
1
,……,v
j
)就有可能是从v
i
到v
j
的中间顶点的序号不大于1的最短路径。将它和已经得到的从v
i
到v
j
中间顶点序号不大于0的最短路径相比较,从中选出中间顶点的序号不大于1的最短路径之后,再增加一个顶点v
2
,继续进行试探。依次类推。
(3)在一般情况下,若(v
i
,……,v
k
)和(v
k
,……,v
j
)分别是从v
i
到v
k
和从v
k
到v
j
的中间顶点的序号不大于k一1的最短路径,则将(v
i
,……,v
k
,……,v
j
)和已经得到的从v
i
到v
j
且中间顶点序号不大于k一1的最短路径相比较,其长度较短者便是从v
i
到v
j
的中间顶点的序号不大于忌的最短路径。这样,在经过n次比较后,最后求得的必是从v
i
到v
j
的最短路径。
(4)按此方法,可以同时求得各对顶点间的最短路径。
转载请注明原文地址:https://kaotiyun.com/show/lyxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列各项中,《凡尔赛和约》没有做出最后规定的是()。
正式制定我国社会主义现代化建设“三步走”战略部署的是()。
清廷为稳定地方统治,严厉裁抑乡绅权力,连续制造了几起大案,不包括()
中共十四届六中全会《关于加强社会主义精神文明建设若干重要问题的决议》,强调要()。
1861年俄国废除农奴制改革的主要作用是()。①造成资本的集中②扩大了国内市场③提供了自由劳动力④强化了中央集权
简述辛亥革命前革命派和改良派论战的主要内容,并谈谈你对这场论战的基本看法。(南京大学2002年综合卷真题)
简述清代秘密立储制的操作并作出评价。
明治维新中,事实上废除了封建领主土地所有制的举措是()。
著名的网络OSI七层模型是由()组织提出来的。
下图所示为双总线结构机器的数据通路,IR为指令寄存器,PC为程序计数器(具有自增功能),M为主存(受R/W信号控制),AR为地址寄存器,DR为数据缓冲寄存器,ALU由加、减控制信号决定完成何种操作,控制信号G控制的是一个门电路。另外,线上标注有小圈表示有控
随机试题
A.肺结核B.特发性肺纤维化C.肺出血一肾炎综合征D.结节病E.肺泡蛋白沉积症以下症状可见于何种疾病进行性呼吸困难,查体杵状指、双肺底闻及Velero啰音。考虑诊断为
A.发热伴胸痛B.发热伴明显的肌肉痛C.发热伴黄疸D.发热伴淋巴结无痛性肿大E.发热伴4天后出皮疹麻疹常为
伴水肿的轻度高血压患者,应首选( )。
B:经营单位应为天津医疗设备有限公司(1207249038)E:贸易方式应为外资设备物品H:成交方式应为CIFI:合同协议号应为2004CAMS-GH098S:总价应为35500美元
甲单位是一家中央级事业单位,执行国库集中支付制度,并于2013年1月1日施行了新的事业单位会计制度。2014年9月,甲单位财务部门对其2014年度的预算编制、预算执行、资产管理、政府采购等进行了全面检查,提出了以下需要进一步研究的事项:(1)201
《小学数学课程标准(2011年版)》中所说的“数学基本思想”主要指(),数学推理思想,数学建模思想。
记住了一首诗之后长时间不去复述就会忘记,这符合同化说理论对遗忘的解释。()
根据下面材料回答问题。2009年普通高中专任教师数最多的三个地区为()。
国家主席胡锦涛开通微博后,在短短的时间内拥有上万的粉丝,你怎样看待这一问题?
【政闻社】清华大学2004年中国近现代史真题;西北师范大学2015年历史学综合真题
最新回复
(
0
)