扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 最短路径中等
单选题
2018年5月第38题
中等
单选题
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。
这个过程正是通过比较所有可能的路径，逐步迭代更新最短路径，最终找出最优解。