2. 考研
  3. 给定A、B、C、D共4个城市之间的单向高速公路，如图6-3所示。图6—3中边上所注的权重为单向高速公路的千米数。现要建立一个应急救护中心，其地点应选择在某城市，使得应急救护中心到最远的城市的高速公路最近，以便应急救护人员能尽快到达。试回答以下问题： 求

给定A、B、C、D共4个城市之间的单向高速公路，如图6-3所示。图6—3中边上所注的权重为单向高速公路的千米数。现要建立一个应急救护中心，其地点应选择在某城市，使得应急救护中心到最远的城市的高速公路最近，以便应急救护人员能尽快到达。试回答以下问题： 求

admin2014-04-17  6
问题 给定A、B、C、D共4个城市之间的单向高速公路，如图6-3所示。图6—3中边上所注的权重为单向高速公路的千米数。现要建立一个应急救护中心，其地点应选择在某城市，使得应急救护中心到最远的城市的高速公路最近，以便应急救护人员能尽快到达。试回答以下问题：

求出每对城市之间到达的最短路径及高速公路的千米数(写出求解的中间过程)。
选项
答案由Dijkstra算法，先求从A到B、C、D的最短距离。 首先，我们发现A到集合{B，C，D}的最短路径为A→B=1，故从A到B的最短距离为1km。然后集合{A，B}到集合{C，D}的最短路径为B→D=2，A直接到D的距离4km，比较发现从AB到BD这个距离相对较短，故从A到D的最短距离为AB+BD=3km。最后集合{A，B，D}到C的距离最短为D→C=6，与其他路径相比，路径A→B→D→C距离短一些，故A到C的最短距离为9km。故 A到B的最短距离为1km。 A到C的最短距离为9km。A到D的最短距离为3km。对其他的路径以此类推，可得B到A的最短距离为11km，路径为B→D→C→A。B到C的最短距离为8km，路径为B→D→C。B到D的最短距离为2km。C到A的最短距离为3km。C到B的最短距离为4km，路径为C→A→B。C到D的最短距离为6km，路径为C→A→B→D。D到A的最短距离为9km，路径为D→C→A. D到B的最短距离为10km，路径为D→C→A→B。D到C的最短距离为6km。
解析
转载请注明原文地址:https://kaotiyun.com/show/Aexi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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