首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下图中的顶点表示村庄,有向边代表交通路线,若要建立一家医院,试问建在哪一个村庄能使各村庄总体交通代价最小?
下图中的顶点表示村庄,有向边代表交通路线,若要建立一家医院,试问建在哪一个村庄能使各村庄总体交通代价最小?
admin
2012-06-26
84
问题
下图中的顶点表示村庄,有向边代表交通路线,若要建立一家医院,试问建在哪一个村庄能使各村庄总体交通代价最小?
选项
答案
该图的邻接矩阵如下: [*] 利用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
学硕统考专业
相关试题推荐
1933年美国通过的《工业复兴法》规定:“雇主不得工人参加何种工会为雇佣条件;必须遵守工时……工资限额。”这一法令说明()
以下改革不属于两河流域的是()
下面属于城市市民的文学作品的是()。
下列科技文化成就,产生于3世纪的是()。①刘徽提出计算圆周率的正确方法②贾思勰著《齐民要术》③钟繇把隶书转化为楷书④马钧发明翻车
1988年起,苏联民族矛盾激化,民族分离运动加剧,第二次较大规模的民族冲突是()。
明治维新废除了封建身份制度,一般武士被归为()。
下列对春秋时期各国称霸的顺序描述错误的选项是()
古希腊是西方文明的发源地,古希腊雅典的民主政治则开启了西方民主制度的先河。下列关于雅典民主政治的说法,符合史实的有()。①民主政治时期的雅典没有国王②公民大会是雅典国家的最高决策机构③伯里克利时期,雅典民主政治达到了顶峰④包
荷兰国旗问题:设有一个仅红、白、蓝三种颜色的条块组成的条块序列,请编写一个时间复杂度为O(n)的算法,使得这些条块按红、白、蓝的顺序排好,即排成荷兰国旗图案。
分页存储管理中,页表的功能是什么?当系统中的地址空间变得非常大时(如32位地址空间),会给页表的设计带来什么样的新问题?请给出一种解决方法,分析它的优点和缺点。
随机试题
A.环氧乙烷B.高压蒸汽C.漂白粉D.过氧乙酸E.苯扎溴铵手术器械灭菌宜选用
关于输卵管妊娠的描述错误的是
复温法是治疗小儿五硬证的重要措施之一,下列哪项不是复温的合理方法
医疗事故处置中,患者有权复制的病历资料不包括
在FOB交货方式下,属于买方的基本义务的是()。
某办公大楼由主楼和裙楼两部分组成,平面呈不规则四方形,主楼29层,裙楼4层,地下2层,总建筑面积81650m2。该工程5月份完成主体施工,屋面防水施工安排在8月份。屋面防水层由一层聚氨酯防水涂料和一层自粘SBS高分子防水卷材构成。裙楼地下室回填土施
现代信用货币包括现金和银行存款两种主要存在形式,其基本特征有()。
《中华人民共和国招标投标法》涵盖工程的________。
小李在Excel中整理职工档案,希望“性别”一列只能从“男”“女”两个值中进行选择,否则系统提示错误信息,最优的操作方法是()。
A、Itdependsonindividualcircumstances.B、Houseworkshouldbedonebywomen.C、Houseworkshouldbedonebytheonewhodonot
最新回复
(
0
)