GESP 八级 · GESP 八级样题（C++ 组） 第 25 题

下图中 A 到 E 的 Dijkstra 单源最短路可以在第 $2$ 次探索中找到。（ ） 

这题考的是 Dijkstra 算法里‘距离更新’和‘最短路确定’的区别。拿到题先别急着算，要盯着算法流程：每次选未处理集合里距离最小的点才算是‘找到’最短路，中间被松弛过的点还在未处理集合里，不能算确定。

最容易掉进命题人的坑就是以为距离值被写进数组就算找到了最短路。Dijkstra 是贪心算法，只有当某个点被从‘未处理集合’里挑出来加入‘已处理集合’时，它的最短路才真正确定。第 2 次探索时 E 的距离确实被更新为 4，但此时 E 还在未处理集合里，后面还会继续比较、松弛，所以不能算找到。

【考点】Dijkstra 算法流程｜最短路确定时机｜贪心策略

GESP 八级《算法与编程》模块，考查图论中 Dijkstra 算法的迭代过程理解。命题人卡住的是八级考生普遍混淆“距离更新”与“最短路确定”的概念——以为距离值被写进数组就算找到了最短路，这是典型的贪心算法初学者误区。

1. 核心思维：何时才算“找到”最短路？

Dijkstra 单源最短路的核心是：每次从未处理集合中选取距离最小的点 u，将其加入已处理集合，再松弛 u 的所有邻点。只有当点被选中加入已处理集合时，它的最短路才真正确定。中间被松弛过的点还在未处理集合里，距离随时可能再变小，不能算“找到”。