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

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

admin2013-12-31  62
问题 下图4-3中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在哪一个村庄能使各村庄总体交通代价最小?
选项
答案该图的邻接矩阵如下： [*] 利用Floyd算法可求得两顶点之间最短路径长度。最后求得： [*] 从A4中可求得每对村庄之间的最少交通代价。假设医院建在i村庄时，其他各村庄往返总的交通代价如下所示： 医院建在村庄0时，各村庄往返总的交通代价为12+1 6+4+7+1 3+1 6+4+18=90； 医院建在村庄1时，各村庄往返总的交通代价为13+29+17+20+12+11+8+5=11 5； 医院建在村庄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时总体交通代价最少。
解析
转载请注明原文地址:https://kaotiyun.com/show/Pvxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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