GESP 八级 · GESP 202406 C++ 八级 第 20 题

在一个包含 $v$ 个顶点、$e$ 条边的带权连通简单有向图上使用 Dijkstra 算法求最短路径，时间复杂度为 $O(v^2)$，可进一步优化至 $O(e + v \log(v))$。

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

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

【考点】Dijkstra 算法｜堆优化｜时间复杂度分析

1. 🎯 考纲定位

GESP 八级算法模块核心内容。命题人专门卡住大量只会背诵「Dijkstra O(v²)」的考生，八级不再满足于写出基本流程，而是考查对算法优化的理解深度。