2. 考研
  3. 下图中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一个村庄能使各村庄总体交通代价最小?

下图中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一个村庄能使各村庄总体交通代价最小?

admin2013-07-12  64
问题 下图中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一个村庄能使各村庄总体交通代价最小?
选项
答案该图的邻接矩阵如下： [*] 利用F1oyd算法可求得两顶点之间最短路径长度。最后求得： [*] 从A4中可求得每对村庄之间的最少交通代价。假设医院建在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算法的基本思想是：
假设求从顶点vi到vj的最短路径。如果从vi到vj，有弧，则从vi到vj存在一条长度为arcs[j]的路径，该路径不一定是最短路径，尚需进行n次试探。
    (1)首先考虑路径(vi，v0，vj)是否存在，即判别弧(vi，v0)和(v0，vj)是否存在。如果存在，则比较(vi，vj)和(vi，v0，vj，)的路径长度，取长度较短者为从vi到v2j，的中间顶点的序号不大于O的最短路径。
    (2)假如在路径上再增加一个顶点v1，也就是说，如果(vi，……，v1)和(v1，……，vj)分别是当前找到的中间顶点的序号不大于0的最短路径，那么(vi，……，v1。，……，vj)就有可能是从vi到j的中间顶点的序号不大于1的最短路径。将它和已经得到的从vi到vj，中间顶点序号不大于O的最短路径相比较，从中选出中间顶点的序号不大于1的最短路径之后，再增加一个顶点v2，继续进行试探。依次类推。
    (3)在一般情况下，若(vi，……，vk)和(vk，……，vj)分别是从vk到vj和从口。到口，的中间顶点的序号不大于k－1的最短路径，则将(vi，……，vk，……，vj)和已经得到的从vi到vj且中间顶点序号不大于k－1的最短路径相比较，其长度较短者便是从vi到vj，的中间顶点的序号不大于k的最短路径。这样，在经过n次比较后，最后求得的必是从vi到vj的最短路径。
    (4)按此方法，可以同时求得各对顶点间的最短路径。
转载请注明原文地址:https://www.kaotiyun.com/show/fuxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)