首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下图中的顶点表示村庄,有向边代表交通路线,若要建立一家医院,试问建在哪一个村庄能使各村庄总体交通代价最小?
下图中的顶点表示村庄,有向边代表交通路线,若要建立一家医院,试问建在哪一个村庄能使各村庄总体交通代价最小?
admin
2012-06-26
87
问题
下图中的顶点表示村庄,有向边代表交通路线,若要建立一家医院,试问建在哪一个村庄能使各村庄总体交通代价最小?
选项
答案
该图的邻接矩阵如下: [*] 利用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
学硕统考专业
相关试题推荐
巴黎和会讨论的中心问题是()。
中华人民共和国恢复了在联合国合法席位的时间是()。
下列各项不是“南北议和”形成的原因的是()。
西藏自治区的设立时间是()。
马克思说:巴黎公社“只不过是在特殊条件下的一个城市起义”。其含义是()。
花剌子密不是()。
材料一从波罗的海斯德丁(什切青)到亚得里亚海边的里亚斯特,一幅横贯欧洲大陆的铁幕已经降落下来……无一不处在苏联的势力范围之内。
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
在某个操作系统中,通过大量的实验,人们观察到在两次缺页中断之间执行的指令数与分配给程序的页框数成正比,即可用内存加倍,缺页中断的平均间隔也加倍。整体缺页次数减少约一半。假设一条普通指令需要100ns,但若发生了缺页中断就需要1ms。一个程序运行了60s,期
光纤分为单模光纤和多模光纤,这两种光纤的区别是()。
随机试题
支配大腿各肌群的神经有:
颈椎病颌枕带牵引最大重量不应超过()
牙根纵裂的X线片中可见,除了()
A.胎产史B.喂养史C.生长发育史D.预防接种史E.家族史需要与传染病鉴别时,应特别注意询问的是()
确定危险源时,更重要的是要充分考虑施工活动三种时态(过去、现在、将来)和三种状态(正常、异常、紧急)下潜在的各种危险。()
()的连线被称为里地线
根据《合同法》的规定,债权人领取提取物的权利期限为()年,超过该期限,提存物扣除提存费用后归国家所有。
公正公平原则是指,证券投资分析师必须在收费标准上一视同仁,不得以资金量大小或交易频率等方面的区别歧视某些投资者或委托机构,在提供咨询意见的深度和准确性上应持统一标准。( )
下列关于现金流量的估计的说法中,错误的是()。
ThemostimportantthingnowisforDemocratsnottopanic.Despitewhatyourgutistellingyou,thisisnottheendofthewor
最新回复
(
0
)