GESP 八级 · GESP 202512 C++ 八级 第 21 题

使用二叉堆优化的 Dijkstra 最短路算法，在某些特殊情况下时间复杂度不如朴素实现的 $ O(V^2) $。

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

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

【考点】Dijkstra 算法｜二叉堆优化｜时间复杂度对比

1. 考纲定位：GESP 八级"图论算法"模块，命题人专门卡住"死记 Dijkstra 复杂度"的考生——堆优化 O(E log V) 看似碾压，却忽略 V² 在稠密图的优势。

2. 解题思维：朴素 Dijkstra 每轮扫描全部顶点找最小距离 O(V²)；改用二叉堆后，每次取最小 O(log V) 但插入/更新仍需 O(log V)，总复杂度 O(E log V)。关键观察：当图边数 E 接近 V²（稠密图）时，log V 因子让堆版本反成 O(V² log V)，慢于朴素版。

3. 陷阱拆解：题干"某些特殊情况"暗指稠密图，命题人利用"堆优化永远更快"的思维定势，设置绝对化表述的陷阱。若只背结论，会误判堆优化在所有图都更优，忽视 V² 在稠密图的实际优势。

4. 反命题思维：如果把"二叉堆"换成"斐波那契堆"或改成"稀疏图"，答案会怎样？提示：刷到类似题先问"命题人想考我什么"，警惕绝对化表述。