最短路径 Dijkstra
Shortest Path
约 16 分钟 · v11
最短路径 Dijkstra
cs-algo/shortest-path · COMP25211 先看：从 A 出发，到每个点最便宜走多少？
把图想成地图：节点是地点，边上的数字是过路费 / 距离。从 A 出发，求到每个点的最便宜总花费。点「下一步」看 Dijkstra 怎么一个点一个点地"敲定"答案——注意 B 的估值会从 6 被改进到 3。
Dijkstra 单步演示（起点 A）
绿 = 已敲定（最短值确定）；蓝虚线 = 还在更新中；橙 = 本步正在处理。∞ = 暂时到不了。
Dijkstra 算法：在边权非负的图上，求一个起点到所有点的最短距离。做法是不断挑出"当前距离最小、还没敲定"的点，敲定它，再用它去松弛（relax）邻居——能更便宜就更新。
"松弛"= 看一条边：如果经过当前点到邻居 比邻居现在的估值还便宜，就更新成更便宜的（B 就这样从 6 被改成 3）。
2 凭什么对：每次敲定"最近的那个"
Dijkstra 是贪心：每一步都敲定当前估值最小的未访问点，并断言"它的值不会再变小了"。为什么这个断言成立？
dist 最小的那个 u。因为边权非负，再绕路只会更贵，所以 u 现在的估值就是它的最终最短距离——可以敲定。u→v：若 dist[u]+w < dist[v]，就把 dist[v] 更新（并记下"v 的上一步是 u"，用来还原路径）。O((V+E) log V)。想要"两点间一条最短路径"而不只是距离？沿着每个点记的"上一步"从终点回溯到起点，就是路径。BFS 是 Dijkstra 在"所有边权 = 1"时的特例。
3 一个致命前提：不能有负权边
Dijkstra 的正确性全压在"挑出的最小值不会再变小"上——而这只在边权非负时成立。
2，A→C 权 5，C→B 权 -4。Dijkstra 会先敲定 B = 2（它当前最小）。可后来经过 C 再走 -4，到 B 其实只要 5 + (-4) = 1 < 2——但 B 已被敲定、不再回头看，于是给出错误答案 2。负权边一出现，"敲定就不再变"的贪心前提就垮了。
有负权边怎么办？用 Bellman–Ford（能处理负权，还能检测"负权环"）。另外：Dijkstra 也不要求图连通，到不了的点距离保持 ∞；BFS 只适用于无权（或等权）图。
4 自测
三道题，点选项即时判对错。
一句话带走：
Dijkstra = 贪心地敲定"当前最近的未访问点"，再松弛它的邻居。每敲定一个点，它的最短距离就定死了；用小根堆挑最小，复杂度 O((V+E) log V)；沿"上一步"回溯得到路径。它的正确性依赖边权非负——有负权边要改用 Bellman–Ford。无权图求最短路，BFS 就够（Dijkstra 的等权特例）。