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

Dijkstra 的算法在实现时一般可以选用（ ）来提高效率？

这题考数据结构在算法里的选型，别死背公式。拿到‘提高效率’四个字，脑子里立刻跳出：原来做法是O(V²)，能不能把最耗时的‘找最小’这一步降下来？数组扫描要O(V)，堆取最小只要O(log V)，这就是核心突破口。

很多学生看到Dijkstra就默认选数组，因为课本例题常这么写，但题目问的是‘提高效率’，这其实是命题人在挖坑，诱导你选常规实现。还有人会纠结链表，觉得存顶点方便，却忘了链表没法快速定位最小值；更有人把栈混进来，完全搞错了贪心的‘最小优先’逻辑。最容易掉进‘堆排序’这个术语陷阱，以为堆就是用来排序的，其实这里是用最小堆做优先队列，功能和排序无关，只负责高效取最小。

这道题考的是‘算法效率优化’与‘数据结构选型’的结合，具体指向Dijkstra算法中如何把‘找最小距离顶点’这一步从O(V)降到O(log V)。命题人专门在GESP八级图算法模块里挖这个坑，就是看你是否真正理解数据结构对时间复杂度的影响，而不是只会套模板。Dijkstra是典型的贪心算法，每一步都要从‘未访问顶点’里挑出距离起点最近的。如果用数组（A），每次都要遍历所有未访问点找最小值，最坏情况总复杂度是O(V²)；如果用链表（B），虽然存图方便，但链表不支持随机访问，找最小依然要O(V)，甚至更慢，属于偷换概念；用栈（D）更离谱，栈是后进先出，完全违背Dijkstra‘最小优先’的贪心策略。只有用堆（C），也就是优先队列，才能把‘找最小’变成O(log V)的操作，整体复杂度压到O(E log V)。所以选C。这里容易踩的坑是术语混淆：堆排序和堆作为优先队列是两回事，题目问的是数据结构功能，不是排序算法，别被‘堆排序’这几个字带偏。考频数据也印证了这一点：算法相关真题总共就7题，覆盖级别少、年份散，说明这类‘数据结构选型’的纯概念题在近年考试里并不常见，但一旦出现，往往就是压轴或关键区分点。基于现有数据，暂无足够依据预测未来具体怎么考，但可以推断：随着图论题目增多，这类考察‘为什么选堆而不是数组’的辨析题可能会以选择题或填空形式回归，重点还是会落在时间复杂度的量级对比上。解题心法就是：看到‘提高效率’，先问‘哪一步最慢？’，再想‘有没有数据结构能把这一步降下来？’，最后核对选项是否真的能实现这个功能。