6.4.2.1 Dijkstra 算法

教材导航 · 第6章

原书定位

印刷页P234起,对应PDF第246页。下文为目视整理的知识提要;完整内容见原书对照。

维护已确定最短距离的集合 final、暂定距离 dist 与前驱 path。每轮从尚未确定的顶点中选 dist 最小者 uu,确定其距离,再松弛其出边:

dist[v]←min⁡(dist[v],dist[u]+w(u,v))dist[v]\leftarrow\min(dist[v],dist[u]+w(u,v))

要求边权非负。源点 dist=0,其余按直达边或无穷初始化;若最小暂定距离已为无穷即可停止。前驱链可恢复路径。

朴素实现 O(n2)O(n^2);仅改成邻接表而仍线性选最小值,不会自动降到 O(n+m)O(n+m)。配合堆可改善稀疏图性能。负边会破坏“取出即最终确定”的贪心依据。

Dijkstra 示例与逐轮距离表

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

负权边使 Dijkstra 失效的例子

负权边使 Dijkstra 失效的例子,原书P236。

对应练习

6.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P234,PDF第246页

原书对照,原书P235,PDF第247页

原书对照,原书P236,PDF第248页