在 Dijkstra 算法中，选择下一个要处理的顶点的规则是什么？

适用条件

• 有分配了距离标签的未圈出顶点。
• 算法在更新邻居后处于选择阶段。

理解与推导

1. 扫描所有未圈出的顶点以获取其暂定距离标签。
2. 识别其中的最小标签。
3. 选择对应该最小标签的顶点。
4. 圈出该顶点以将其标记为已确定。
5. 从其前驱画一个箭头以记录路径。
6. 继续更新这个新确定顶点的邻居。

例子

在视频中，初始化家之后，未圈出的顶点是 $A (2)$ 和 $C (3)$。最小的是 A 处的 2，所以 A 被圈出。后来，在未圈出的顶点 $B (6)$、$C (3)$、$D (4)$、$E (4)$ 中，最小的是 C 处的 3，所以 C 被圈出。演讲者说：“现在我们寻找写在图上的最小未圈出数字。在这种情况下是二，所以我们要把它圈起来……”

容易误解的地方

• 选择距离最大的顶点。
• 选择已经圈出的顶点。
• 忽略距离标签并随机选择。

观看对应讲解

继续追问

• 在 Dijkstra 算法中，如何更新当前圈出顶点的邻居？
• 为什么 Dijkstra 算法在目标标签 7 首次出现时不立即将其最终确定？
• 在 Dijkstra 算法演示中，顶点处的数字标签和蓝色圆圈代表什么？