GESP 八级 · GESP 202509 C++ 八级 第 11 题

下列 Dijkstra 算法，假设图 graph 中顶点数 $v$、边数 $e$，则程序的时间复杂度为（ ）。

typedef struct Edge {
    int in, out;   // 从下标in顶点到下标out顶点的边
    int len;       // 边长度
    struct Edge * next;
} Edge;
// v: 顶点个数, graph: 出边邻接表, start: 起点下标, dis: 输出每个顶点的最短距离
void dijkstra(int v, Edge * graph[], int start, int * dis) {
    const int MAX_DIS = 0x7fffffff;
    for (int i = 0; i < v; i++)
        dis[i] = MAX_DIS;
    dis[start] = 0;
    int * visited = new int[v];
    for (int i = 0; i < v; i++)
        visited[i] = 0;
    visited[start] = 1;
    for (int t = 0; ; t++) {
        int min = MAX_DIS, minv = -1;
        for (int i = 0; i < v; i++) {
            if (visited[i] == 0 && min > dis[i]) {
                min = dis[i];
                minv = i;
            }
        }
        if (minv < 0)
            break;
        visited[minv] = 1;
        for (Edge * e = graph[minv]; e != NULL; e = e->next)
            if (dis[e->out] > e->len)
                dis[e->out] = e->len;
    }
    delete[] visited;
}

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

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

【考点】朴素 Dijkstra 算法｜邻接表存储｜时间复杂度分析

解题思维：外层循环固定执行 v 次，内层找最小值需 O(v) 扫描，松弛操作总计 O(e)。整体 O(v²+e)=O(v²)。命题人故意用朴素写法而非优先队列，这是 C++ 八级图论模块的经典考点——让学生识别"最短路算法的朴素实现"与"堆优化版本"的本质区别。

陷阱拆解：选项 B/C/D 全是堆优化的复杂度特征。B 项是斐波那契堆理论最优解，C 项是二叉堆版本，D 项是 BFS 或 Dijkstra 的线性扫描版本（但 D 要求边权非负且用邻接表时仍要 O(v²)）。题目中的 visited 数组线性扫描找最小值，不借助任何堆结构，这是铁证。很多考生死记"最短路用堆"就选 C，忽略了这道题代码本身没有用堆。

反命题思维：若把 graph 改成邻接矩阵，复杂度仍是 O(v²)；若把找最小值改成优先队列，答案会变 C。命题人想考你：看到 Dijkstra 代码先判断实现方式，而非直接套用公式。刷到类似题，先问自己"有没有堆"。