首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下图中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一个村庄能使各村庄总体交通代价最小?
下图中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一个村庄能使各村庄总体交通代价最小?
admin
2013-07-12
39
问题
下图中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一个村庄能使各村庄总体交通代价最小?
选项
答案
该图的邻接矩阵如下： [*] 利用F1oyd算法可求得两顶点之间最短路径长度。最后求得： [*] 从A
4
中可求得每对村庄之间的最少交通代价。假设医院建在i村庄时，其他各村庄往返总的交通代价如下所示： 医院建在村庄0时，各村庄往返总的交通代价为12＋16＋4＋7＋13＋16＋4＋18＝90： 医院建在村庄1时，各村庄往返总的交通代价为13＋29＋17＋20＋12＋11＋8＋5＝115： 医院建在村庄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
)和(v
0
，v
j
)是否存在。如果存在，则比较(v
i
，v
j
)和(v
i
，v
0
，v
j
，)的路径长度，取长度较短者为从v
i
到v
2j
，的中间顶点的序号不大于O的最短路径。
(2)假如在路径上再增加一个顶点v
1
，也就是说，如果(v
i
，……，v
1
)和(v
1
，……，v
j
)分别是当前找到的中间顶点的序号不大于0的最短路径，那么(v
i
，……，v
1
。，……，v
j
)就有可能是从v
i
到
j
的中间顶点的序号不大于1的最短路径。将它和已经得到的从v
i
到v
j
，中间顶点序号不大于O的最短路径相比较，从中选出中间顶点的序号不大于1的最短路径之后，再增加一个顶点v
2
，继续进行试探。依次类推。
(3)在一般情况下，若(v
i
，……，v
k
)和(v
k
，……，v
j
)分别是从v
k
到v
j
和从口。到口，的中间顶点的序号不大于k－1的最短路径，则将(v
i
，……，v
k
，……，v
j
)和已经得到的从v
i
到v
j
且中间顶点序号不大于k－1的最短路径相比较，其长度较短者便是从v
i
到v
j
，的中间顶点的序号不大于k的最短路径。这样，在经过n次比较后，最后求得的必是从v
i
到v
j
的最短路径。
(4)按此方法，可以同时求得各对顶点间的最短路径。
转载请注明原文地址:https://kaotiyun.com/show/fuxi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
不仅主张通过三种国家权力的分立达到相互制衡的目的，而且提出通过国家与地方政府的分权更好地实施对权力的制约的思想家是()。
相比较而言，下列最不能代表资产阶级利益和资本主义发展方向的是()
《关于建国以来党的若干历史问题的决议》对毛泽东和毛泽东思想历史地位的科学评价。
下列叙述正确的是()。
戊戌政变发生的时间是()。
文艺复兴时期，系统提出了国家主权理论的政治思想家是()。
在五四运动至新中国成立前这一时期，实际上可供中国人民选择的建国方案主要是()。
在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。
什么是域名解析?域名解析中采取了什么措施提高效率?对同一个域名向DNS服务器发出多次的DNS请求报文后，得到IP地址都不一样，可能吗?为什么?
一个公司有两个部门，研发部和市场部，研发部有29台计算机，市场部有11台计算机。现在，公司申请了一个C类地址212．112．32．0，规划的网络拓扑如图1一5所示。试问：根据第一题的规划，请为两个部门各分配一个子网网络地址，并为两个路由器的接口和各台
随机试题
临床确诊牙髓坏死的最有效检查是
根据《民事诉讼法》的有关规定，对本寒有管辖权的法院是()。如果本案经第二审人民法院审理并作出终审判决，广角音像公司败诉，但其拒绝履行义务，红星电视剧制作中心欲申请执行，有管辖权的法院是()。
如果某产品市场占有率和行业成长率都较高，产品有发展潜力，企业又有竞争力，则该产品应是企业重点发展的业务。在波士顿矩阵分析中，这种业务被称为()。
背景资料：某地区新建一座大型自来水厂，主要单位工程有沉淀池、过滤池、消毒池等，整个工程由A建筑公司中标施工。其中沉淀池为无盖圆形池，直径为40m，基础为现浇混凝土结构，厚为500mm，该基础由四周向中心呈漏斗型，其高点顶面标高为22．50m，低点
影响幼儿操作技能形成的因素有()。
社会主义教育的理论基础是()
12．7，20．9，31．1，43．3，()
Individualsandbusinesseshavelegalprotectionforintellectualpropertytheycreateandown.Intellectualproperty【C1】______c
堆是______。
A------pricetermJ------timeofshipmentB------costandfreightK------businessnegotiationC------importlicenseL------purc
最新回复
(
0
)
