CSP-S 2020 第一轮 第14题：对一个n个顶点、m条边的带权有向简单图用Dijkstra算法计算单源最短

题目

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

选项

• A. $O((m + n^2) \log n)$
• B. $O(mn + n^3)$
• C. $O((m + n) \log n)$
• D. $O(n^2)$

答案

D

题解

答案选 D. \(O(n^2)\)。

不使用堆或优先队列时，Dijkstra 算法的主要操作是：

1. 选出距离源点最近的未确定顶点：每次需要扫描所有顶点，耗时 \(O(n)\)；共进行至多 \(n\) 次，因此耗时 \(O(n^2)\)。
2. 更新相邻顶点的距离（松弛）：使用邻接表时，每条边最多被检查一次，总耗时 \(O(m)\)。

所以总时间复杂度为 \[ O(n^2+m). \] 有向简单图中 \(m\le n(n-1)\)，因此可化简为 \(O(n^2)\)。