https://www.youtube.com/watch?v=pSqmAO-m7Lk

单源最短路径,指定一个起点,计算到其它节点的最短路径。

example

初始情况如下,我们求从 0 号节点到其它节点的最短路径。

初始化将 (0, 0) 加入到 priority queue,并将 dist[0] 设置为 0

Untitled

从 priority queue 中取出第一个访问的节点 0, 该节点有两个分支,分别是 1 和 2 节点,将 1 和 2 节点加入 priority queue,下次迭代时访问(BFS)

在 dist 数组中更新 0 到 1、2 节点的距离

Untitled

接下来,从 priority queue 选择(2, 1)

2 号节点有两个分支,分别是 1 和 3 号节点

0 → 2 → 1 的距离小于 0 → 1, 更新 dist 数组中 1 的值

更新 priority queue,加入 (1, 3)

Untitled

0 → 3 的路径长度为 6, 更新 dist 3 为 6,并将 (3,6)插入 priority queue