首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
下图中的顶点表示村庄,有向边代表交通路线,若要建立一家医院,试问建在哪一个村庄能使各村庄总体交通代价最小?
下图中的顶点表示村庄,有向边代表交通路线,若要建立一家医院,试问建在哪一个村庄能使各村庄总体交通代价最小?
admin
2012-06-26
86
问题
下图中的顶点表示村庄,有向边代表交通路线,若要建立一家医院,试问建在哪一个村庄能使各村庄总体交通代价最小?
选项
答案
该图的邻接矩阵如下: [*] 利用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
学硕统考专业
相关试题推荐
清廷为稳定地方统治,严厉裁抑乡绅权力,连续制造了几起大案,不包括()
相比较而言,下列最不能代表资产阶级利益和资本主义发展方向的是()
以下对于清初恢复发展经济的措施论述正确的一项是()。①停止圈地②“更名田”③奖励垦荒④整顿赋役制度⑤废除匠籍
关于伯里克利时代的叙述,不正确的是()。
辽国规定中央官职中的()一律由契丹贵族担任。
对资本主义萌芽出现起决定性作用的明朝农业生产特点是()。
到1869年为止,人类已发现了多少种化学元素()。
明治维新中,事实上废除了封建领主土地所有制的举措是()。
完整地表述电磁场理论的物理学家是()。
拟建设一个光通信骨干网络连通BJ、CS、XA、QD、JN、NJ、TL和WH等8个城市,图中无向边上的权值表示两个城市间备选光纤的铺设费用。请回答下列问题。假设每个城市采用一个路由器按计算总费用中得到的最经济方案组网,主机H1直接连接在TL的路由器上
随机试题
下列哪项不是药物避孕的反应( )。
交感神经的作用
某建设项目的工程费与工程建设其他费的估算额为52180万元,预备费为5000万元,项目的投资方向调节税率为5%,建设期3年。3年的投资比例是:第1年20%,第2年55%,第3年25%,第4年投产。该项目固定资产投资来源为自有资金和贷款。贷款的总额
下列属于从事技术、风险监控、合规管理人员可以从事的工作是()。
下列关于财产保全的表述,错误的是()。
甲会计师事务所2007年10月1日承接了甲公司2007年度财务报表的审计业务,2008年3月5日完成审计工作,2008年3月10日出具审计报告,假设该鉴证业务预期不会再度发生,则该项业务的业务期间为( )。下列选项中,说法正确的是( )。
新中国成立至20世纪60年代初,监狱关押改造的罪犯主要是()。
结构化分析方法是一种面向下列哪项的需求分析方法?
假设CD盘片的存储容量为600MB,上面存放的数字图像能以每秒25幅画面、每幅画面为360×240×65536色的分辨率播放1小时,则CD盘片上的数字图像的压缩比大约是______。
Aglobe-spanningU.N.digitallibraryseekingtodisplayandexplainthewealthofallhumancultureshasgoneintooperationon
最新回复
(
0
)