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

admin2007-10-11  34

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


选项 A、3
B、4
C、5
D、6

答案A

解析 本题可以用简单连通无向图中两结点间的最短路径求解算法解答,也可以通过给图中每条边均赋权值1后,然后用(55)的求解方法解答。但是要注意,“转弯”次数比最短路径长度少1。
转载请注明原文地址:https://kaotiyun.com/show/DOQZ777K
0

最新回复(0)