查看更多
当前 - 选择题 - 最短路径
中等
单选题
2018年5月第38题
#数学与经济管理
#最短路径
#第二版教材
#凯恩建议必须掌握

下表记录了六个结点A、B、C、D、E、F之间的路径方向和距离。从A到F的最短距离是(__)。

问题(1)
正确答案A
凯恩解析

本题实际上是求最短路径的问题
迪杰斯克拉迭代法最为方便,就是逐个求出A到该点的最短距离。

我们从A开始,起始时A到每个节点的最短距离是:

  • A → A: 0
  • A → B: 11
  • A → C: 16
  • A → D: 24
  • A → E: 36
  • A → F: 54

A → B的直接路径是11,所以A到B的最短路径是11。

从A到C有两种路径:

  1. 直接从A到C,距离是 16
  2. 从A到B,再从B到C,路径是 A → B → C = 11 + 13 = 24
    所以 A → C的最短路径是16,直接从A到C。

不断迭代,到最后可以知道 A → F的最短路径是38。
这个过程正是通过比较所有可能的路径,逐步迭代更新最短路径,最终找出最优解。

联系我们
隐私协议
用户协议
微信公众号
知乎
小红书
浙ICP备2021029036号
@2022-2026
嘉兴市安芯网络科技有限公司 版权所有