2. 计算机
  3. 11个城市之间的公路交通网络以及每条公路长度如下图所示。从城市s到城市t的最短距离为(55)　；现引入“转弯”的定义如下：在从s旅行到t的过程中，每从一条公路转到另一条公路上时称进行了一次转弯，从城市s到城市t最少经过(56)次转弯。

11个城市之间的公路交通网络以及每条公路长度如下图所示。从城市s到城市t的最短距离为(55)　；现引入“转弯”的定义如下：在从s旅行到t的过程中，每从一条公路转到另一条公路上时称进行了一次转弯，从城市s到城市t最少经过(56)次转弯。

admin2007-10-11  47
问题 11个城市之间的公路交通网络以及每条公路长度如下图所示。从城市s到城市t的最短距离为(55)　；现引入“转弯”的定义如下：在从s旅行到t的过程中，每从一条公路转到另一条公路上时称进行了一次转弯，从城市s到城市t最少经过(56)次转弯。
选项 A、92
B、82
C、81
D、73
答案C
解析 本题是一个典型的图论算法的应用问题。既可以看作赋权简单连通无向图的单源问题进行求解，也可以用两结点间最短距离算法进行求解。
   采用单源问题的迪克斯特拉(E．W Dijkstra)算法求解。
   将题图中未标记的结点进行标记，得到下图：
  
   令S={s}，T={a，b，c，d，e，f，S，h，i，t}，
   D(s)=0，D(a)=25，D(b)=21，D(c)=+∞，  D(d)=+∞，D(e)=+∞，D(f)=+∞，
   D(g)=+∞，  D(h)=+∞，  D(i)=+∞，  D(t)=+∞。
    因为D(b)=21是T中最小的D值，选x=b，令S ←S∪{X}={s,b}。
   令T ←T-{X}={a，d，c，d，e，f，g，h，i，t},然后计算：
   D(a)=min(25，21+23)=25，D(c)=min(+∞，21+20)=41，D(d)=min(+∞，21+25)=46，
   D(e)=min(+∞，+∞)=+∞，D(f)=min(+∞，+∞)=+∞，D(g)=min(+∞，+∞)= +∞，
   D(h)=min(+∞，+∞)=+∞，D(i)=min(+∞，+∞)=+∞，D(t)=min(+∞，+∞)= +∞。
   如此类推，直到T=终止，整个过程概括于表如下：
  
D(t)=81，所以城市s到城市t的最短距离为81。
转载请注明原文地址:https://kaotiyun.com/show/xOQZ777K
本试题收录于： 系统分析师上午综合知识考试题库软考高级分类
0

系统分析师上午综合知识考试

软考高级

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