Dijkstra 算法

2026 大纲 五（四）图的基本应用 2. 最短路径 · 单源带权（无权图见《BFS 最短路径》，全源见《Floyd》）。

一个看起来很像、其实是错的贪心

先看一个直觉上很自然的做法。要从源点走到目标点，那就：

① 当前顶点设为源点；② 选一个离当前顶点最近且还没走过的顶点，走过去，把当前顶点更新成它；③ 重复，直到到达目标点。

这个方法不对，而且反例小到只要四个顶点：$S\to A$ 权 1、$A\to T$ 权 10、$S\to B$ 权 3、$B\to T$ 权 1。

从 $S$ 出发，离 $S$ 最近的是 $A$（权 1），走过去；再从 $A$ 走到 $T$（权 10）。总长 11。而真正的最短路是 $S\to B\to T$，长度只有 4。

错在哪？这个贪心是近视的：它每一步只看"离当前顶点多近"，而最短路径要求的是"离源点多近"。第一步贪了那个 1，把自己锁进了一条后半段极贵的路。

Dijkstra 把"当前顶点"换成"源点"，问题就解决了：

🔴 每轮在尚未确定的顶点中，选 dist 最小的那个——dist[v] 是"从源点到 $v$ 的当前已知最短距离"，不是"到刚才那个顶点的距离"。

先动手看一眼

加载可视化中...

盯两件事：一是每轮被选中的那个顶点，它的 dist 之后再也不变；二是每轮选中顶点的 dist 单调不减。这两条是手算时的自检线，也是下面正确性证明的两个支点。

贪心为什么这次对了

命题：每轮选出的"未访问顶点中 dist 最小的 $u$"，其 dist[u] 就是源点到 $u$ 的真实最短距离。

证明（反证）。设 $S$ 为已确定集合，$u$ 是 $V-S$ 中 dist 最小者。假设真实最短距离 $\delta (u)<dist[u]$，那么这条更短的路径上必有第一个落在 $V-S$ 中的顶点 $x$（因为起点 $v_0\in S$、终点 $u\in V-S$）。$x$ 之前的顶点全在 $S$ 中，所以 $dist[x]$ 早在 $x$ 的前驱并入 $S$ 时就被松弛到位，即 $dist[x]=\delta (x)$。

又因所有边权非负，从 $x$ 到 $u$ 那一段长度 $\ge 0$，故

$$dist[x]=\delta (x)\le \delta (u)<dist[u]$$

这说明 $V-S$ 中存在 dist 比 $u$ 更小的顶点，与"$u$ 最小"矛盾。∎

🔴 "边权非负"用在的确切位置就是 $\delta (x)\le \delta (u)$ 那一步：只有非负权才保证"路径越走越长"，从而"先确定的不会被后来的路径改短"。允许负权，这一步立刻失效。

注意条件是 $\ge 0$ 而不是 $>0$——0 权边 Dijkstra 完全可以处理。"非负"和"正"是两个条件，别混。

算法实现

#define INF 0x3f3f3f3f

int graph[MAX_V][MAX_V], dist[MAX_V], visited[MAX_V], path[MAX_V];

void dijkstra(int n, int src) {
    for (int i = 0; i < n; i++) { dist[i] = INF; visited[i] = 0; path[i] = -1; }
    dist[src] = 0;
    path[src] = src;              // 约定源点前驱是自己，作为回溯的终止标志

    for (int i = 0; i < n; i++) {
        int u = -1, minDist = INF;            // ① 选最小
        for (int j = 0; j < n; j++)
            if (!visited[j] && dist[j] < minDist) { minDist = dist[j]; u = j; }
        if (u == -1) break;       // 剩余顶点 dist 全为 INF → 都不可达，提前结束
        visited[u] = 1;           // ② 确定：u 就此钉死，之后不再改动

        for (int v = 0; v < n; v++)           // ③ 松弛 u 的未访问邻接点
            if (!visited[v] && graph[u][v] != INF
                && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
                path[v] = u;
            }
    }
}

三个数组分工明确：dist[v] 答"多远"、path[v] 答"怎么走"（记前驱）、visited[v] 保证每个顶点只被确定一次。

两处实现细节：

• 🔴 INF 取 0x3f3f3f3f 而不是 INT_MAX：前者约 $1.06\times {10}^9$ 足够大，且 INF + INF 仍不溢出 int；取 INT_MAX 则 INF + w 溢出成负数——"无穷大加一点"反而变成最小值，松弛会做出完全相反的判断。
• graph[u][v] != INF 必需，拦住"根本没有边"。松弛条件里的 dist[u] != INF 则可写可不写——u == -1 的提前 break 已保证选中的 $u$ 可达。

与 Prim 的对照：两者骨架几乎一样，Prim 用的是 lowcost[v] = min(lowcost[v], cost[u][v])，量的是 $v$ 到树的距离，不累加；Dijkstra 用的是 dist[u] + w(u,v)，量的是到源点的距离，要累加。少了那个 dist[u] +，"最短路径"就变成了"最小生成树"。

手算：真题问的是"确定顺序"和"某一轮的 dist"

这一节的选择题几乎只有两种问法，做法是同一套。

问法一：依次得到的各最短路径的目标顶点是（即顶点被"钉死"的先后顺序）。 问法二：求出第 $k$ 条最短路径后，dist 数组的内容更新为（某一轮结束时的快照）。

手算流程画一张表，每行一轮，列是各顶点的 dist：

1. 初始化：源点 0，其余 $\mathrm{\infty }$。
2. 每轮先在未确定的顶点里挑 dist 最小的，把它圈起来（这就是"第 $k$ 条最短路径的目标顶点"）。
3. 用刚圈中的顶点的每一条出弧去松弛，更新未确定顶点的 dist。
4. 回到第 2 步。

⚠️ 第 3 步是失分的重灾区：新加入的顶点，它的每一条出弧都要拿来松弛一遍，一条都不能漏。 真题里有一道就卡在这儿——某个顶点的 dist 本该在第 2 轮由新入选顶点的一条出弧更新成有限值，漏了这一步它就一直是 $\mathrm{\infty }$，到最后比较时排序整个错位。

两条自检随手可用：

• 已确定顶点的 dist 不再变。 手算时若改动了一个已圈中的值，说明前面某步选错了点。
• 每轮选中顶点的 dist 单调不减。 出现回落，一定算错了。

并列最小选谁？ 任选。这不影响 dist[]（它是图的固有量），但可能影响 path[]——最短路径可以不唯一。

六顶点有向图的逐轮推演（想手动模拟一遍就展开）

弧与权：$0\to 1$ 权 10、$0\to 3$ 权 30、$0\to 4$ 权 100、$1\to 2$ 权 50、$3\to 2$ 权 20、$3\to 4$ 权 60、$2\to 4$ 权 10、$5\to 0$ 权 5。

顶点 5 只有出弧、没有入弧，所以从 0 出发到不了 5——正好检验"不可达"分支。求源点 $0$ 到其余各顶点的最短路径（加粗表示该顶点已确定）：

轮次	选中 $u$	$dist[0]$	$dist[1]$	$dist[2]$	$dist[3]$	$dist[4]$	$dist[5]$	本轮松弛
初始	—	0	∞	∞	∞	∞	∞	—
1	0	0	10	∞	30	100	∞	$0\to 1,0\to 3,0\to 4$
2	1	0	10	60	30	100	∞	$1\to 2$：$10+50=60$
3	3	0	10	50	30	90	∞	$3\to 2$：$30+20=50$；$3\to 4$：$30+60=90$
4	2	0	10	50	30	60	∞	$2\to 4$：$50+10=60$
5	4	0	10	50	30	60	∞	无出弧
6	无	0	10	50	30	60	∞	提前结束

path[] 的同步变化：

轮次	$path[0]$	$path[1]$	$path[2]$	$path[3]$	$path[4]$	$path[5]$
初始	0	−1	−1	−1	−1	−1
1	0	0	−1	0	0	−1
2	0	0	1	0	0	−1
3	0	0	3	0	3	−1
4	0	0	3	0	2	−1
5–6	0	0	3	0	2	−1

每轮选中顶点的 dist 依次是 $0,10,30,50,60$，确实单调不减；已加粗的值此后再没变过。

路径回溯：

void printPath(int path[], int dest) {
    if (path[dest] == dest) { printf("%d", dest); return; }   // 到达源点
    if (path[dest] == -1)   { printf("(不可达)"); return; }
    printPath(path, path[dest]);      // 先打印前驱一侧，天然正序
    printf(" → %d", dest);
}

还原 $0\to 4$：$path[4]=2\to path[2]=3\to path[3]=0\to path[0]=0$（到源点，停），得 $0\to 3\to 2\to 4$，验算 $30+20+10=60=dist[4]$ ✓。它既不是权 100 的直连弧，也不是第 2 轮临时算出的 $0\to 1\to 2$——中途被改过两次前驱的顶点，正是手算最容易写错的地方。

若改用 path[src] = -1 的约定，回溯的终止条件要相应改成 v != -1；两种写法各自自洽，不能混用。

负权边反例的逐步执行（想看清它在第几轮、因为什么而错就展开）

三顶点有向图：$0\to 1$ 权 5，$1\to 2$ 权 $-3$，$0\to 2$ 权 3。

轮次	选中 $u$	$dist[0]$	$dist[1]$	$dist[2]$	说明
初始	—	0	∞	∞
1	0	0	5	3	松弛 $0\to 1$ 得 5；$0\to 2$ 得 3
2	2	0	5	3	未访问中 $dist[2]=3$ 最小，选中并永久确定为 3
3	1	0	5	3	松弛 $1\to 2$：$5+(-3)=2<3$，但 $visited[2]$ 已为真，不会更新

真实答案是 $0\to 1\to 2$ 长度 $5+(-3)=2$。错在第 2 轮："顶点 2 当前 dist 最小，所以它已最优"——这个推断的隐含前提是"后面再怎么绕路都只会更长"，负权边打破了它。

两种复杂度各自的来历（想在给定 n 和 e 下选实现方式就展开）

朴素 $O(n^2)$：外层 $n$ 轮，每轮线性扫描找最小（$O(n)$）+ 扫邻接矩阵一整行做松弛（$O(n)$）。与边数无关——即使只有 $n-1$ 条边，矩阵每行仍要扫满。

堆优化 $O(e\log n)$：邻接表 + 最小堆。松弛至多 $e$ 次、每次调堆 $O(\log n)$，合计 $O(e\log n)$；取最小 $n$ 次合计 $O(n\log n)$。两项相加 $O((n+e)\log n)$，连通图上 $e\ge n-1$ 故简写为 $O(e\log n)$。

指标	朴素（邻接矩阵）	堆优化（邻接表 + 最小堆）
时间	$O(n^2)$	$O(e\log n)$
空间	$O(n)$ 辅助 + $O(n^2)$ 存图	$O(n)$ 辅助 + $O(n+e)$ 存图
适合	稠密图（$e$ 接近 $n^2$）	稀疏图（$e\ll n^2$）

要代数比较，不要背：$e\approx n^2$ 时 $e\log n=n^2\log n>n^2$，朴素更优；$e\approx n$ 时 $e\log n=n\log n\ll n^2$，堆优化更优。

求全源：对每个顶点各跑一次即 $n\times O(n^2)=O(n^3)$，与 Floyd 同阶，但 Floyd 形式更简单且能处理负权边。

负权边的三条边界

• 含负权边、无负权回路 → Dijkstra 会答错，改用 Bellman-Ford，或用 Floyd 求全源。
• 含负权回路 → 最短路径根本不存在（绕一圈就更短，可以无限减小）。这不是算法不行，是问题无解。
• 含 0 权边 → Dijkstra 完全可以处理。

考点速记

三条结论：

1. 每轮选的是"离源点最近"的未确定顶点，不是"离当前顶点最近"的。 后者是一个会答错的近视贪心。
2. 贪心正确性 = 边权非负 ⇒ 路径越走越长 ⇒ 先确定的不会被改短；0 权无妨，负权失效。
3. $O(n^2)$ 与边数无关（宜稠密图），$O(e\log n)$ 与边数线性相关（宜稀疏图）；跑 $n$ 次即 $O(n^3)$，与 Floyd 同阶。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

• 确定顶点的先后顺序：问"依次得到的各最短路径的目标顶点是"，或给出前两个再问"后续依次是"。逐轮画 dist 表，每轮圈一个最小值。
• 某一轮的 dist 数组快照：问"求出第二条最短路径后，dist 中的内容更新为"。注意"第二条"意味着已经确定了两个顶点（不含源点），要数清楚停在第几轮。
• 举反例否定一个错误贪心（大题）：题面给出"每次选离当前顶点 $u$ 最近的顶点并入"这套做法，问能否求得最短路径，若不能请举例说明。答案是不能，反例要给出一张具体的带权图并算出两条路径的长度对比——四顶点就够：$S\to A=1,A\to T=10,S\to B=3,B\to T=1$，该方法得 11，真实最短是 4。
• 作为最短路径树的算法出现在跨科目综合题里：给一张网络拓扑与链路费用，要求算出某个路由器到各网络的最短路径树。

易错：每轮松弛时，新入选顶点的每一条出弧都要用上。 漏掉其中一条，某个顶点的 dist 会停在 $\mathrm{\infty }$ 或偏大的值上，导致后面几轮的选中顺序整个错位——这是"确定顺序"类题目的头号错因。

易错："离当前顶点最近"是错的贪心，"离源点最近"才是 Dijkstra。 两者只在源点那一轮重合，从第二轮起就分道扬镳。

易错：已确定的顶点不再更新。 手算时若发现要改一个已圈中的值，回头查前面选点是不是选错了；若图里真有负权边，那就是 Dijkstra 不适用，不是你算错了。

易错："非负"不等于"正"，0 权边不影响 Dijkstra。

教材出处

• 严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p171，§6.6.2： 把顶点分成两组——"第一组 $S$：已求出的最短路径的终点集合（初始时只包含源点 $v_0$）； 第二组 $V-S$：尚未求出最短路径的顶点集合"， "算法将按各顶点与 $v_0$ 间最短路径长度递增的次序，逐个将集合 $V-S$ 中的顶点加入到集合 $S$ 中去"； 同页用反证法证明"下一条最短路径……或者是边 $(v_0,x)$， 或者是中间只经过 $S$ 中的顶点而最后到达顶点 $x$ 的路径"。
• 同书印刷 p171：算法的辅助数据结构——一维数组 S[i] 记录终点 $v_i$ 是否已确定最短路径长度。
• 同书印刷 p174（算法分析）： "求解最短路径的主循环共进行 $n-1$ 次，每次执行的时间是 $O(n)$，所以算法的时间复杂度是 $O(n^2)$。 如果用带权的邻接表作为有向图的存储结构，则虽然修改 $D$ 的时间可以减少， 但由于在 $D$ 向量中选择最小分量的时间不变，所以时间复杂度仍为 $O(n^2)$。"
• 同书印刷 p174：求每一对顶点之间的最短路径的两种方法—— 调用 $n$ 次迪杰斯特拉算法，或采用弗洛伊德算法，"两种算法的时间复杂度均为 $O(n^3)$， 但后者形式上较简单"。

相关知识

BFS 最短路径（无权图特例，三算法选型表在那一篇）｜ Floyd 算法（全源，可处理负权边）｜ Prim 算法（骨架相同，只差松弛式是否累加）｜ 邻接矩阵（朴素实现的存储前提）｜ 堆（堆优化用它维护最小 dist）｜ 图的基本概念（带权路径长度与"距离"）

相关文章

• 图的基本概念
• 邻接矩阵
• 邻接表
• 十字链表与邻接多重表
• 广度优先搜索（BFS）
• 深度优先搜索（DFS）
• 最小生成树：Prim
• 最小生成树：Kruskal
• BFS 求无权图最短路径
• Floyd 算法
• DAG 描述表达式
• 拓扑排序
• 关键路径

交互体验

前往完整可视化页面 →

真题练习

相关真题（5题）

2021Q82分2016Q82分2014Q4210分2012Q72分2009Q4110分