2. 计算机
  3. A、B、C、D、E、F、G代表七个村落，村落之间的道路连通情况如下图所示(边上的数据为距离，单位为公里)。这七个村落拟合建一所小学，已知A村有小学生50人、B村有小学生40人、C村有小学生60人、D村有小学生20人、E村有小学生70人、F村有小学生80、G

A、B、C、D、E、F、G代表七个村落，村落之间的道路连通情况如下图所示(边上的数据为距离，单位为公里)。这七个村落拟合建一所小学，已知A村有小学生50人、B村有小学生40人、C村有小学生60人、D村有小学生20人、E村有小学生70人、F村有小学生80、G

admin2018-10-14  66
问题 A、B、C、D、E、F、G代表七个村落，村落之间的道路连通情况如下图所示(边上的数据为距离，单位为公里)。这七个村落拟合建一所小学，已知A村有小学生50人、B村有小学生40人、C村有小学生60人、D村有小学生20人、E村有小学生70人、F村有小学生80、G村有小学生100人。则拟合建的小学应建在(    )村落，才能使学生上学所走的总路程最短。
选项 A、C村
B、A村
C、F村
D、E村
答案D
解析 这是一个最短路径问题，需要使用Dijkstra最短路径算法。
Dijkstra算法的基本思路是：若序列(vs，v1，v2，…，vt—1，vt)是从vs到vt的最短路径，则序列(vs，v1，v2，…，vt—1)必为从vs到vt—1的最短路径。
首先，计算各村之间相互的最短距离，从而得出一个到达矩阵，如下表所示，第一行代表从A到所有村庄的最短距离，第二行代表从B到所有村庄的最短距离，以此类推……

注意，该表格是沿对角线对称的，所以只需构造一半，然后讲另一半复制上即可。

再用各村的学生人数乘该村所在行的数据，例如，A的人数乘以这个到达矩阵的第
  一行，B的人数乘以第二行，以此类推……
上表的最后一行为：小学建在某村时，所有小学生上学时所走的总路程。
设dX表示学校建在X时，学生上学所走的最短总路程，则：
  dA=1864，dB=1771，dC=1958，dD=1656
  dE=1408，dF=1623，dG=1616
小学建在E村时，学生上学所走的总路程最短。
转载请注明原文地址:https://www.kaotiyun.com/show/0vFZ777K
本试题收录于： 信息系统项目管理师上午综合知识考试题库软考高级分类
0

信息系统项目管理师上午综合知识考试

软考高级

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