Dijkstra 算法
Dijkstra 算法的主要思想是贪心。它的流程是:
将所有节点分成两类:已确定从起点到当前点的最短路长度的节点,以及未确定从起点到当前点的最短路长度的节点(下面简称「未确定节点」和「已确定节点」)。
每次从「未确定节点」中取一个与起点距离最短的点,将它归类为「已确定节点」,并用它「更新」从起点到其他所有「未确定节点」的距离。直到所有点都被归类为「已确定节点」。
用节点 A「更新」节点 B 的意思是,用起点到节点 A 的最短路长度加上从节点 A 到节点 B 的边的长度,去比较起点到节点 BBB 的最短路长度,如果前者小于后者,就用前者更新后者。这种操作也被叫做「松弛」。
这里暗含的信息是:每次选择「未确定节点」时,起点到它的最短路径的长度可以被确定。
可以这样理解,因为我们已经用了每一个「已确定节点」更新过了当前节点,无需再次更新(因为一个点不能多次到达)。而当前节点已经是所有「未确定节点」中与起点距离最短的点,不可能被其它「未确定节点」更新。所以当前节点可以被归类为「已确定节点」。
定义 g[i][j]
表示节点 i
到节点 j
连接的边的权重,如果没有从 i
到 j
的边,则 g[i][j]=♾️
。
定义 dis[i]
表示节点 k
到节点 i
的最短路径的长度。在最开始,dis[k]=0
(自己到自己的路径为 0),其余路径 dis[i]=♾️
,表示尚未计算出。
Dijkstra 的目标是计算出最终的 dis
数组。
- 首先更新节点
k
到它的邻居y
的最短路,即更新dis[y]
为g[k][y]
; - 然后取除了节点
k
以外的dis[i]
的最小值,假设当i=j
时dis[j]
的值是dis[i]
中最小的; - 用节点
j
到它的邻居y
的边权g[j][y]
更新dis[y]
,如果dis[j]+g[j][y]<dis[y]
,就更新dis[y]
,否则不更新; - 取除了节点
k,j
以外的dis[i]
的最小值,循环以上过程; - 即可求得每个点的最短路。
743. 网络延迟时间和3112. 访问消失节点的最少时间是很不错的经典 Dijkstra 和堆优化的 Dijkstra 示例,可以参考。