2. 计算机
  3. 下图中，从A到E的最短长度是( )(图中每条边旁的数字为该条边的长度)。

下图中，从A到E的最短长度是( )(图中每条边旁的数字为该条边的长度)。

admin2018-10-14  66
问题 下图中，从A到E的最短长度是(    )(图中每条边旁的数字为该条边的长度)。
选项 A、17
B、18
C、19
D、20
答案B
解析 这题考的是两点之间的最短路径问题。
本题的解决思路很简单：合并简化，将原图由5层图简化成如下的3层图(利用Dijkstra最短路径算法的思想：最短路径的任意一段都是局部最优的)，即可目测得出：网络图的最短路径是A→C1→E，全路径是A→B2→C1→D1→E，长度为18。

简化过程是：
  从A到C1：min{5+7，6+3}=9。
  从A到C2：min{5+6，6+5}=11。
  从A到C3：min{5+4，6+7}=9。
  从A到D1：min{9+6，11+6，9+7}=15。
  从A到D2：min{9+9，11+6，9+9}=17。
  从A到E：min{15+3，17+5}=18。
转载请注明原文地址:https://kaotiyun.com/show/SvFZ777K
本试题收录于： 信息系统项目管理师上午综合知识考试题库软考高级分类
0

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

软考高级

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