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 示例，可以参考。