单源最短路的 O(n²) 实现 —— Dijkstra 朴素版

原始题目

下面这段 C++ 代码实现的是哪个算法？

int graph[N][N];
int dist[N];
bool visited[N];
void dijkstra(int start, int n) {
    memset(dist, 0x3f, sizeof(dist));
    dist[start] = 0;
    for (int i = 1; i <= n; i++) {
        int u = -1;
        for (int j = 1; j <= n; j++) {
            if (!visited[j] && (u == -1 || dist[j] < dist[u])) u = j;
        }
        // ___ 这里常考一个关键判断 ___
        visited[u] = true;
        for (int v = 1; v <= n; v++) {
            if (!visited[v] && graph[u][v]) {
                dist[v] = min(dist[v], dist[u] + graph[u][v]);
            }
        }
    }
}

选项：

A. Floyd 最短路径
B. Dijkstra 最短路径（朴素版）
C. Bellman-Ford 最短路径
D. 最小生成树

答案

B. Dijkstra 最短路径（朴素版）

解析

这段代码有 Dijkstra 的三个标志性特征：

1. 单源距离数组 dist[]：dist[start]=0，其余初始化为 INF（0x3f3f3f3f）。
2. 已确定集合 visited[]：每轮选择一个点 u，标记为 visited[u]=true，表示它的最短距离已经确定。
3. 松弛操作：dist[v] = min(dist[v], dist[u] + graph[u][v])，用当前点 u 去更新邻居 v 的距离。

Floyd 是多源最短路，会用到三重循环；Bellman-Ford 会逐条边松弛 n-1 轮；最小生成树则用 Prim 或 Kruskal，不会维护“到起点距离”的 dist[]。

一个最小执行示例

假设图如下，起点为 1：

执行过程：

最终 dist = [0, 2, 3, 4]，即从 1 到 4 的最短距离为 4。

常考填空：缺失的关键守卫

上面代码里有一个必须补上的安全判断：

if (u == -1) break;   // 选无可选时立即退出

当剩余未访问节点全不可达时，u 会保持 -1。若不加这句，随后 visited[u]=true 会访问 visited[-1]，造成数组越界或未定义行为，轻则算错、重则段错误。

易错点总结

• 朴素 Dijkstra 时间复杂度：O(n²)，适合稠密图或 n 较小（通常 ≤ 几千）。
• 边权必须非负：Dijkstra 不能处理负权边。
• 邻接矩阵判断边：if (graph[u][v]) 默认边权非 0，若存在 0 权边会误判。

思考题

下面代码能否把 if (!visited[j] && ...) 里的 !visited[j] 去掉，只保留 dist[j] < dist[u]？为什么？