首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下图中的顶点表示村庄,有向边代表交通路线,若要建立一家医院,试问建在哪一个村庄能使各村庄总体交通代价最小?
下图中的顶点表示村庄,有向边代表交通路线,若要建立一家医院,试问建在哪一个村庄能使各村庄总体交通代价最小?
admin
2012-06-26
113
问题
下图中的顶点表示村庄,有向边代表交通路线,若要建立一家医院,试问建在哪一个村庄能使各村庄总体交通代价最小?
选项
答案
该图的邻接矩阵如下: [*] 利用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://www.kaotiyun.com/show/lyxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
德、意两个法西斯国家领土连成一片是在()事件之后。
20世纪30年代的国联的所作所为,反映的实质问题是国联()
建国初期,为稳定社会秩序和恢复经济,人民政府最迫切需要解决的问题是()。
20年代国际关系的中心是()。
中国境内已发现的猿人化石不包括()。
西藏自治区的设立时间是()。
洋务派创办军事工业的方式是()。
北宋在统一南方割据势力的过程中特设(),把征南所得的财富统一存放,以作日后恢复幽燕之费。
下列的网络协议中,()的运输层协议是使用TCP的。
设有A,B,C,D4台主机都处在同一个物理网络中,A主机的IP地址是192.155.28.112,B主机的IP地址是192.155.28.120,C主机的IP地址是192.155.28.135,D主机的IP地址是192.155.28.202。共
随机试题
女性,34岁。乏力、面色苍白、尿色黄1年。贫血貌,巩膜黄染。脾肋下2指。血清总胆红素37μmol/L,间接胆红素27tμmol/L,肝功能正常。Hb65g/L,白细胞7.5×109/L,血小板170×109/L。网织红细胞10%。该患者
与配体结合后,自身具有酪氨酸蛋白激酶活性的受体是
彩色多普勒血流显像仪的性能,下列哪项与之无关
女,3个月,发热、咳嗽3天,抽搐2次。查体:精神反应差,前囟饱满,呼吸节律不整,口周发青,双下肺满布小水泡音,心音低钝,心率180次/分。肝脏肋下5cm,右巴氏征(+)。如患儿的脑脊液检查不正常,诊断与哪项相关
A.0.15~0.3gB.0.3~0.9gC.0.9~1.5gD.1.5~5gE.5~10g
下列哪一项不属于外汇市场的功能?()
道德教育的__________是当代德育理论中流行最为广泛、占据主导地位的德育学说。
考虑社会中一个典型消费者的效用函数为U(x1,x2)=lnx1+3lnx2,x1、x2分别是商品1和商品2的消费量,该消费者收入为1000元,两种商品价格都是1。(2016年中国人民大学802经济学综合)比较上述两种措施对消费者效用的影响,哪种情况下
Readthefollowingtextfromamagazinearticleinwhichfivepersonstalkedabouttheproblemofgreenhouseeffectandglobalw
FixingaWorldThatFostersObesityA)WhyareAmericansgettingfatterandfatter?Thesimpleexplanationisthatweeattoomuc
最新回复
(
0
)