6.4.2.1 Dijkstra 算法
原书定位
印刷页P234起,对应PDF第246页。下文为目视整理的知识提要;完整内容见原书对照。
维护已确定最短距离的集合 final、暂定距离 dist 与前驱 path。每轮从尚未确定的顶点中选 dist 最小者 ,确定其距离,再松弛其出边:
要求边权非负。源点 dist=0,其余按直达边或无穷初始化;若最小暂定距离已为无穷即可停止。前驱链可恢复路径。
朴素实现 ;仅改成邻接表而仍线性选最小值,不会自动降到 。配合堆可改善稀疏图性能。负边会破坏“取出即最终确定”的贪心依据。

Dijkstra 示例与逐轮距离表,原书P235。

负权边使 Dijkstra 失效的例子,原书P236。
对应练习
关联知识
原书对照
展开原书对照截图


