GESP 八级 · GESP 202509 C++ 八级 第 24 题

Dijkstra 算法的时间复杂度为 $O(V^2)$，其中 $V$ 为图中顶点的数量。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】图论最短路径｜算法复杂度分析｜数据结构优化

考纲定位：GESP八级《图论与最短路径》模块。命题人专攻死记结论的考生——只背“最短路算法”就认为复杂度固定的学生，一遇到变式就栽跟头。

解题思维：看到Dijkstra先想数据结构：用数组找最小值要O(V)循环，总复杂度O(V²)；用优先队列优化后变O((V+E)logV)。命题人把“数组版”当唯一答案，就是考你知不知道还有更优实现。这题本质是考你对算法实现的敏感度，而不是死记硬背。

陷阱拆解：选项A说“是O(V²)"纯属偷换概念——只谈数组实现却忽略优先队列版本，这题最阴险的细节是“算法”二字没限定实现方式。如果你只背结论、不理解本质，就会掉进这个陷阱：以为所有Dijkstra都是O(V²)，遇到图很大还硬套数组版就超时了。命题人故意用绝对化表述来卡住你，优先队列版才是竞赛标准实现。

反命题思维：若改成“优先队列版Dijkstra复杂度”，答案就变A；若改成“稠密图Dijkstra复杂度”，答案又变A。刷到类似题先问自己：命题人想考我什么——是考实现差异，还是考边界条件？这题就是考你能不能跳出“算法=数组实现”的思维定式。