Dijkstra 算法
复习
- 无权图的最短路径：BFS 第一次到达即最短
- 优先队列：每次取出最值
- 图：带权图
TL;DR
- Dijkstra 求带权图（非负权）的单源最短路
- 它每次选出当前距离最小的未确定节点
- 借助优先队列，能高效地选出这个节点
- 一旦出现负权边，它可能给出错误答案
正文
带权图上求最短路，最经典的算法是 Dijkstra 算法。它的思路，是从起点一圈圈“确定”最近的节点。
贪心地确定最近的
先用一个直觉来理解：
- 起点到自己的距离是 0，到其他节点暂时未知（记作无穷大）
- 在所有“还没确定”的节点里，挑出当前距离最小的那个，认为它的最短距离已经确定
- 用它去更新它邻居的距离：如果“经过它再到邻居”比原来更近，就更新
- 重复，直到所有节点都确定
第 3 步叫松弛（relaxation）：不断用新确定的信息，去缩短通往其他节点的估计距离。
为什么可以“确定”
关键问题：凭什么敢说“当前距离最小的那个节点，就已经是最短了”？
因为它已经是最小的了。如果还有一条更短的路能到它，那条路一定要经过某个还没确定的节点；而那些节点的当前距离都不比它小，再加上非负的边权，只会更远。所以不可能有更短的走法，可以放心确定。 这里的“非负”很关键。
用优先队列加速
“每次挑出距离最小的未确定节点”这件事，正好是优先队列的用武之地：把节点按当前距离放进优先队列，每次弹出最小的那个。
于是，Dijkstra 就借助优先队列高效地运转起来。这也再次说明：算法与数据结构是搭档——好的算法，往往需要合适的数据结构才能高效落地。
它怕负权
Dijkstra 有一个硬性前提：所有边权都不能为负。
前面那套“放心确定”的推理，依赖“越走只会越远”。可如果存在负权边，绕远路反而可能让总代价变小，那个“当前最小的节点已经被确定”的假设就崩了，算法可能给出错误答案。
遇到负权边，就要换别的算法了——下一章来看。
思考题 1
Dijkstra 为什么敢“确定”当前距离最小的那个节点？
思考题 2
为什么 Dijkstra 不能处理负权边？
小结
知识点
- Dijkstra 求非负权图的单源最短路
- 每次确定当前距离最小的未确定节点
- 用松弛操作更新邻居距离
- 借助优先队列高效选取最小节点
参考资料
- Wikipedia(zh)：戴克斯特拉算法：非负权图的单源最短路算法
- Wikipedia(zh)：优先队列：Dijkstra 中选取最小距离节点所用
思考题答案（仅供参考）
思考题 1
因为它是当前所有未确定节点里距离最小的。任何更短的路径都要经过某些未确定节点，而那些节点的距离都不比它小，再加上非负边权只会使总代价更大。所以不可能存在更短路径，可以放心确定。
思考题 2
因为负权边破坏了“越走越远”的前提。绕道经过负权边，可能让总代价比当前估计更小，于是“当前最小节点已确定”的结论不再成立，算法可能提前确定错误的最短距离。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪