GESP 八级 · GESP 202603 C++ 八级 第 6 题

在一个有向带权图中，使用 Dijkstra 算法求单源最短路径时，若使用优先队列（小根堆）优化，其时间复杂度为（ ）。

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

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

【考点】贪心算法｜优先队列优化｜图论算法

命题人卡住的是死记硬背算法的学生——很多考生只背过朴素 Dijkstra 的 O(V²) 版本，根本不知道优先队列可以把取点优化到 O(log V)。

看到题先想算法流程：Dijkstra 每次要选当前距离最小的点（取点），然后遍历该点的所有边进行松弛。朴素实现用数组扫描取点需 O(V)，松弛每条边需 O(1)，总复杂度 O(V² + E)。但题目明确说用优先队列，那就把 O(V) 的取点换成堆的 O(log V)，O(1) 的松弛也变成 O(log V)（因为更新堆要查），总复杂度 O((V + E) log V)。

A 是朴素算法，B 是 Floyd 或 BFS 的复杂度，D 是瞎乘 V² 和 log V 的陷阱。最阴险的是 D——如果你只背结论、不理解本质，就会以为"堆优化"就是把 O(V²) 乘以 log V，其实堆优化只是把取点从 O(V) 降到 O(log V)，松弛从 O(1) 升到 O(log V)，综合下来就是 (V + E) log V。

反命题思维：如果把图改成稠密图（E≈V²），答案还是 C；如果用斐波那契堆，复杂度会变成 O(V log V + E)，但题目只说了"优先队列"，默认就是二叉堆。刷到类似题先问："原算法瓶颈在哪？这个数据结构优化的是哪一步？"