首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下图中的顶点表示村庄,有向边代表交通路线,若要建立一家医院,试问建在哪一个村庄能使各村庄总体交通代价最小?
下图中的顶点表示村庄,有向边代表交通路线,若要建立一家医院,试问建在哪一个村庄能使各村庄总体交通代价最小?
admin
2012-06-26
38
问题
下图中的顶点表示村庄,有向边代表交通路线,若要建立一家医院,试问建在哪一个村庄能使各村庄总体交通代价最小?
选项
答案
该图的邻接矩阵如下: [*] 利用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
学硕统考专业
相关试题推荐
1876年7月第一国际举行最后一次代表大会宣告解散,这次代表大会的地点是()。
对《魏玛宪法》的内容和影响叙述不正确的是()。
圣德太子“宪法十七条”规定的是()
导致俄国革命去和平发展可能的事件是()。
二战以来,资本主义经济在发展中出现了许多新问题,主要原因是()。
试析淝水之战前后南北政权的特点和变化。
希拉克略王朝的军区制改革的内容和意义。
以德国宗教改革为例分析宗教改革产生的原因和作用。
所罗门死后不久,以色列犹太王国遂分裂为北方的以色列王国和南方的犹太王国。后来,两国分别为哪两个国家所灭?()
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用getev
随机试题
Fordecadesthemarketforexpensiveheadphoneswasmainlylimitedtohi-fifans.But【C1】________theboxystereosysteminthec
生豆浆中主要含有龙葵碱。()
某城市地下铁道工程的土层渗透系数为5m/d,其透水性属于()。
屋面防水工程、有防水要求的卫生间、房间和外墙面的防渗漏,最低保修期限为()。
关于证券市场从无到有发展的主要原因,下列说法错误的是()。
人力资本投资分析的现代奠基人是()。
薪酬水平一般的企业应注意()点处的薪酬水平。
蜂房的蜜流出来了,吸引了很多苍蝇来吃蜜。因为蜂蜜太香了。它们都舍不得离开。不久这些贪吃的苍蝇都因脚被蜂蜜粘住而飞不走了。请谈谈你的看法。
(2013年浙江)下列词语中,没有错别字的一项是()。
软件按功能可以分为:应用软件、系统软件和支撑软件(或工具软件)。下面属于应用软件的是( )。
最新回复
(
0
)