CSP-S 提高级 · CSP 2020 提高级第一轮 第 14 题

对一个 $n$ 个顶点、$m$ 条边的带权有向简单图用 Dijkstra 算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（ ）。

这道题就是考朴素 Dijkstra 和堆优化版的复杂度区别。拿到题先抓关键词'不使用堆'，直接锁定数组实现：外层 n 轮确定点，每轮扫一遍找最小点 O(n)，再扫一遍边做松弛 O(m)，合起来就是 O(n²+m)，简单图里 m≤n²，最终答案就是 O(n²)。

最容易栽跟头的是把堆优化的复杂度套上去，选成 O((m+n)log n) 或者 O((m+n²)log n)，题目既然专门强调'不使用堆'，那就是在考数组实现的 O(n²) 这个常识。其次是混淆'总复杂度'和'每轮复杂度'，误以为每轮 O(n) 就代表总 O(n)，其实还要乘 n 轮。另外有些同学会纠结'松弛操作要不要算进去'，其实松弛是 O(m) 的，加在 O(n²) 上还是 O(n²)，别被细节绕晕。

考点直击

本题核心就是 Dijkstra 算法两种实现方式的时间复杂度对比。命题人特意强调'不使用堆'，就是要你直接分析朴素数组版的开销。

概念拆解

Dijkstra 求单源最短路，核心是'贪心'：每次从未确定最短路的点里挑距离最小的，然后用它去'松弛'邻居。朴素版不用堆，就用一个数组存所有点的当前距离，每轮暴力扫一遍数组找最小值。