NOIP 提高组初赛 · NOIP 2013 提高组初赛试题 第 14 题

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

这题核心就是看 Dijkstra 没堆优化时怎么找最小值。每次要在所有未访问点里线性扫描找最小 dist，扫一遍 O(n)，一共扫 n 次，所以主项是 n²；松弛所有边是 O(m)，合起来 O(n²+m)，稠密图时 n² 占主导，直接选 B。

最容易掉进两个坑：一是把堆优化的复杂度 O((m+n)logn) 当成默认，忘了题干明确说“不使用堆或其它优先队列”；二是看到有 m 条边就下意识加 O(m) 以为总复杂度是 O(n²+m)，但在大 O 记号里 m 最多是 n² 量级，所以 O(n²+m) 等价于 O(n²)，很多人会纠结要不要写 O(n²+m) 或者误选 C。

考点与概念

这道题考查的是 Dijkstra 算法在不使用堆（优先队列）优化时的时间复杂度。首先要明确朴素版 Dijkstra 的两步操作： 1. 找最小：在尚未确定的顶点集合中，线性扫描找出距离源点最近的顶点。这个集合初始有 n 个点，每次确定一个后规模减一，扫描代价分别是 n, n-1, ..., 1，加起来是 O(n²)。 2. 松弛边：对刚选出的顶点的所有出边执行松弛操作。整个过程中每条边最多被松弛一次，总代价是 O(m)。

命题视角

命题人喜欢在这里挖“限定条件”的坑：题干特意强调“不使用堆或其它优先队列”，就是为了把复杂度锁定在朴素版 O(n²+m)，而不是堆优化后的 O((m+n)logn)。如果学生一看到 Dijkstra 就条件反射选 C，就掉进这个陷阱了。