扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 最短路径中等
单选题
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有两种路径:
- 直接从A到C,距离是 16。
- 从A到B,再从B到C,路径是 A → B → C = 11 + 13 = 24。
所以 A → C的最短路径是16,直接从A到C。
不断迭代,到最后可以知道 A → F的最短路径是38。
这个过程正是通过比较所有可能的路径,逐步迭代更新最短路径,最终找出最优解。
