复习位置数据结构第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到C2 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当前A0, B2, C5, D∞, E∞未确定顶点中最小的是B所以确定B。从B继续松弛到C213 5 所以C更新为3 到D224 所以D更新为4此时A0, B2, C3, D4, 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继续松弛。更新顶点21 - 5 - 2 距离 6 15 21比当前25更短所以dist[2] 21更新顶点41 - 5 - 4 距离 6 8 14所以dist[4] 14检查顶点31 - 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((VE)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等年份。 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到C2 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当前A0, B2, C5, D∞, E∞未确定顶点中最小的是B所以确定B。从B继续松弛到C213 5 所以C更新为3 到D224 所以D更新为4此时A0, B2, C3, D4, 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继续松弛。更新顶点21 - 5 - 2 距离 6 15 21比当前25更短所以dist[2] 21更新顶点41 - 5 - 4 距离 6 8 14所以dist[4] 14检查顶点31 - 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((VE)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等年份。