GESP 八级 · GESP202609 C++ 八级 第 19 题

使用邻接表存储图时，Dijkstra 算法的朴素实现（不使用堆优化）的时间复杂度为 O(V^2)，其中 V 为结点数。

朴素 Dijkstra 用数组存最短距离，每次都要遍历所有顶点找未访问的最小值，外层循环 V 次，内层找最小值 O(V)，合计 O(V²)。邻接表只是存边，不影响找最小值的开销。

把朴素 Dijkstra 和堆优化版混淆，误以为 O(E+VlogV)；或认为邻接表会改变找最小值的复杂度。

1. 考纲定位

本题考查《GESP 考试大纲》八级"图算法"模块中的 Dijkstra 算法复杂度分析。命题人卡住的是考生对"朴素实现"与"堆优化实现"的区分能力——八级考生容易把两种实现混为一谈，误以为只要用邻接表存图，复杂度就会自动变成 O(E+VlogV)。

2. 解题思维

朴素 Dijkstra 的核心操作是：维护一个数组 dist[] 记录各点到源点的最短距离，每次从所有未访问顶点中找出 dist 最小的那个。这个"找最小"的动作必须线性扫描全部 V 个顶点，耗时 O(V)。外层循环要执行 V 次（每轮确定一个顶点的最短距离），所以总复杂度是 V×O(V)=O(V²)。

邻接表的作用仅仅是存储边，遍历邻接表时每条边只会被访问一次，总耗时 O(E)。但"找最小"这一步完全不依赖邻接表，所以 O(V²) 的瓶颈不会改变。