408数据结构第6章：迪杰斯特拉（Dijkstra）算法——真题精讲
复习位置：数据结构第6章 图 -> 最短路径 -> Dijkstra算法
目标：搞清楚“每轮选谁、怎么更新、什么时候不能用”，然后用408真题把流程走一遍。
一、Dijkstra到底是干什么的
Dijkstra解决的是：
单源最短路径问题也就是：
给定一个源点s 求s到其余各顶点的最短路径最重要的使用条件：
边权必须非负有向图和无向图都可以用，但如果存在负权边，就不能直接使用Dijkstra。
二、核心思想只记一句
每一轮选当前距离源点最近、且还没有“确定”的顶点， 把它的最短距离正式确定下来， 再用它去更新周围顶点的距离。可以压缩成六个字：
选最小，做松弛1. 什么叫“选最小”
假设当前：
dist[B] = 2 dist[C] = 5 dist[D] = 8B还没有被确定，并且它的dist最小，那么本轮先选B。
一旦B被选中，在非负权图中：
源点 -> B 的最短路径已经最终确定以后不会再改。
2. 什么叫“松弛”
假设：
dist[B] = 2 B -> C 的边权 = 1 当前 dist[C] = 5经过B到C：
2 + 1 = 3比原来的5更短，所以更新：
dist[C] = 3这就是松弛。
三、Dijkstra的核心公式
对已经确定的顶点u，检查它的邻接点v：
如果： dist[u] + w(u,v) < dist[v] 那么： dist[v] = dist[u] + w(u,v)为了最后能够还原路径，通常还会同时记录：
prev[v] = u意思是：
目前到达v的最短路径，是从u过来的四、标准做题流程
考试时可以直接按下面五步做：
1. 初始化： 源点dist = 0 其余顶点dist = ∞ 确定集合S = 空 2. 在所有未确定顶点中， 找dist最小的顶点u 3. 将u加入S 此时u的最短路径正式确定 4. 用u去松弛所有邻接点v 5. 重复步骤2~4最核心的是：
每轮先“确定”一个点 再从这个点向外更新五、一个小例子
假设：
A -> B = 2 A -> C = 5 B -> C = 1 B -> D = 2 C -> E = 1源点是A。
初始化：
A = 0 B = ∞ C = ∞ D = ∞ E = ∞从A出发第一次松弛：
B = 2 C = 5当前：
A=0, B=2, C=5, D=∞, E=∞未确定顶点中最小的是B，所以确定B。
从B继续松弛：
到C：2+1=3 < 5 所以C更新为3 到D：2+2=4 所以D更新为4此时：
A=0, B=2, C=3, D=4, E=∞接下来选C，再继续更新。
这就是Dijkstra最核心的执行过程。
六、408真题：2021年第8题
2021年408数据结构第8题直接考了Dijkstra执行过程。
题目给出一个有向图，从顶点1出发，各边为：
1 -> 5，权6 1 -> 2，权26 1 -> 3，权3 5 -> 2，权15 5 -> 4，权8 5 -> 3，权6 4 -> 3，权6 4 -> 2，权1 3 -> 2，权22题目问：
使用Dijkstra算法， 求出第二条最短路径后， dist[2], dist[3], dist[4], dist[5]更新为什么？七、真题解题过程
源点是1，所以先初始化：
dist[1] = 0根据顶点1的直接出边，可以得到：
dist[2] = 26 dist[3] = 3 dist[4] = ∞ dist[5] = 6因此初始的未确定距离为：
2 -> 26 3 -> 3 4 -> ∞ 5 -> 6其中最小的是：
dist[3] = 3所以第一条被确定的最短路径目标顶点是3。
接下来用顶点3松弛邻接点。顶点3只有一条到2的边：
3 -> 2，权22经过3到2的距离：
3 + 22 = 25原来：
dist[2] = 26所以更新：
dist[2] = 25现在：
dist[2] = 25 dist[3] = 3 dist[4] = ∞ dist[5] = 6未确定顶点中最小的是：
dist[5] = 6所以第二条被确定的最短路径目标顶点是5。
然后用5继续松弛。
更新顶点2
1 -> 5 -> 2 距离 = 6 + 15 = 21比当前25更短，所以：
dist[2] = 21更新顶点4
1 -> 5 -> 4 距离 = 6 + 8 = 14所以：
dist[4] = 14检查顶点3
1 -> 5 -> 3 距离 = 6 + 6 = 12但：
dist[3] = 3不需要更新。
因此，求出第二条最短路径以后：
dist[2] = 21 dist[3] = 3 dist[4] = 14 dist[5] = 6最终：
[21, 3, 14, 6]这道题真正考的就是：
每确定一个顶点， 立刻用它的出边做一次松弛。八、408最常考的三种Dijkstra题
题型1：问“下一轮选哪个顶点”
只做一件事：
在未确定顶点中找dist最小值谁最小，就选谁。
题型2：问“某轮以后dist数组是什么”
固定步骤：
先确定本轮最小顶点 再对它的邻接点进行松弛 最后写dist2021年第8题就是这种。
题型3：问最终最短路径或最短路径长度
需要一路做到所有目标点确定。
如果还要求输出具体路径，就要记录：
prev[]例如松弛成功：
dist[C]由5更新成3 原因是B -> C那么记录：
prev[C] = B最终从目标结点一路向前回溯即可。
九、Dijkstra为什么不能有负权边
Dijkstra的核心假设是：
当前最小dist的未确定顶点一旦被选中， 它的最短距离以后不会再变小。这个结论依赖：
后续边权 >= 0如果存在负权边，后面可能绕一条路回来，把已经“确定”的距离进一步减小。
于是Dijkstra“确定后不再修改”的策略就会失效。
所以看到：
负权边立刻判断：
不能直接用Dijkstra十、Dijkstra和Floyd不要混
| 算法 | 解决的问题 |
|---|---|
| Dijkstra | 一个源点到其他所有顶点 |
| Floyd | 任意两个顶点之间 |
记忆：
Dijkstra：单源 Floyd：任意两点十一、时间复杂度
408常见写法：
邻接矩阵 + 普通实现
O(n^2)邻接表 + 优先队列/堆优化
O((V+E)logV)在408选择题中，重点还是理解：
每轮找最小dist + 松弛邻接边十二、考场最容易错的地方
1. 选完最小点，却忘记松弛
正确流程一定是：
选点 -> 确定 -> 松弛2. 把“当前最短距离”当最终结果
未加入确定集合S之前：
dist只是临时最短距离只有顶点被本轮选中后：
它的最短距离才正式确定3. 更新时拿错基准
必须比较：
dist[u] + w(u,v)而不是只看边权w(u,v)。
4. 有负权边还使用Dijkstra
看到负权边直接警觉。
十三、考场30秒模板
看到Dijkstra题，在草稿纸上先写：
S = 空 dist[s] = 0 其他 = ∞然后循环：
找最小未确定点u ↓ u加入S ↓ 检查u的邻接点 ↓ dist[u]+边权 < dist[v] ? ↓ 是：更新dist[v]十四、一句话背诵
Dijkstra：每轮选最小的未确定顶点， 把它正式确定下来， 再用它去松弛邻接点。进一步压缩：
选最小，做松弛； 非负权，单源最短路。十五、回去复习的位置
408数据结构 -> 第6章 图 -> 图的应用 -> 最短路径 -> Dijkstra算法重点掌握：
dist数组 确定集合S 每轮选最小 松弛操作 路径前驱prev 负权边限制 Dijkstra与Floyd区别十六、强化阶段的判断标准
如果你看到一张图，能够不看答案独立写出：
轮次 | 本轮确定顶点 | S | dist[A] dist[B] dist[C]...并且每一轮都能正确完成松弛，那么Dijkstra这部分基本就掌握了。
如果仍然经常出现：
不知道本轮选谁 不知道什么时候更新dist 把临时距离当最终距离说明应该回去重新做2~3道“执行过程表格题”，而不是继续背定义。
真题依据：2021年全国硕士研究生招生考试计算机学科专业基础综合（408）数据结构第8题。Dijkstra相关题型在408中还曾出现在2009、2012、2014、2016等年份。