扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 最短路径简单
单选题
2019年5月第31题
简单
单选题
2019年5月第31题
#第二版教材
#必须掌握
下表记录了六个结点A、B、C、D、E、F之间的路径方向和距离。从A到F的最短距离是（38）。
问题（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。
这个过程正是通过比较所有可能的路径，逐步迭代更新最短路径，最终找出最优解。