首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下图中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一个村庄能使各村庄总体交通代价最小?
下图中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一个村庄能使各村庄总体交通代价最小?
admin
2012-06-26
97
问题
下图中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一个村庄能使各村庄总体交通代价最小?
选项
答案
该图的邻接矩阵如下： [*] 利用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
学硕统考专业
相关试题推荐
匈牙利社会主义革命中，之所以能顺利建立苏维埃社会主义共和国的主要原因是()。
第一次从理论上说明热机运行过程、建立热力学原理的是()。
正式制定我国社会主义现代化建设“三步走”战略部署的是()。
德国法西斯能够通过合法方式夺取政权，主要原因有()。①垄断资产阶级要求建立极权统治②纳粹党利用了人民对现状的不满③骗人的宣传欺骗了社会的信任④通过国会纵火案打击了共产党
三国时期，三国称帝的先后顺序是()。
下列关于第三次科技革命的说法，不正确的是()。
“文化大革命”发动的两个纲领性文件是()。
波兰三次被瓜分的时间是()
北宋在统一南方割据势力的过程中特设()，把征南所得的财富统一存放，以作日后恢复幽燕之费。
三个进程P1、P2、P3互斥使用一个包含N(N＞O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用getev
随机试题
补中益气汤中，君药是补中益气汤中，协助人参、黄芪补气养血和营者为
治疗滞颐，可用下列哪味中药研粉敷于涌泉穴()
患者，28岁，妊娠39周，于某日14：23正常经阴道分娩。18：40病人主诉腹胀、腹痛。视诊：下腹膀胱区隆起；叩诊：耻骨联合上浊音。病人存在的健康问题是
按照对利率的预期来调整债券投资组合持续期,将会给资产管理人带来出色的表现,而不会带来较大的损失。()
学习不只是要让学生掌握一门学科或几门学科的具体的知识与技能，而且还要让学生学会如何学习，即掌握___________。
关于陈述性知识，下列说法正确的是()。
关于综合课程，下列说法正确的是()
OurvisittotheexcavationofaRomanfortonahillnearCoventrywasofmorethanarchaeologicalinterest.Theyear’sdighad
使用软件开发工具有助于提高软件的开发、维护和管理的效率。集成型软件开发环境通常由工具集和环境集成机制组成。这种环境应具有______。环境集成机制主要有数据集成机制、控制集成机制和界面集成机制。
A、 B、 C、 B
最新回复
(
0
)
