在 Dijkstra 算法中，如何更新当前圈出顶点的邻居？

适用条件

• 有一个当前的圈出（已确定）顶点。
• 该顶点有尚未圈出的邻居。
• 边权重已知且非负。

理解与推导

1. 识别当前圈出的顶点及其距离标签。
2. 列出该顶点的所有尚未圈出的邻居。
3. 对于每个未访问的邻居，将边权重添加到当前顶点的距离。
4. 将得到的和作为暂定标签写在邻居旁边。
5. 如果邻居已经有标签，将新和与旧标签进行比较。
6. 保留较小的值，必要时划掉较大的值。
7. 如果标签被更新，从当前顶点向邻居画一个前驱箭头。

例子

在视频中，从圈出的顶点“家”（距离 0），邻居 A 和 C 被更新。到 A 的边权重是 2，所以 $0 + 2 = 2$ 写在 A 处。到 C 的边权重是 3，所以 $0 + 3 = 3$ 写在 C 处。后来，从 A（距离 2），B 被更新：$2 + 4 = 6$。

容易误解的地方

• 将边权重添加到邻居的现有标签，而不是当前顶点的标签。
• 更新已经圈出的邻居。
• 忘记与现有标签比较，只是覆盖它们。

观看对应讲解

继续追问

• 在家到大学的示例中，Dijkstra 算法的初始化步骤是什么？
• 在 Dijkstra 算法期间，如何处理单个顶点处的多个距离值？
• 在 Dijkstra 算法演示中，顶点处的数字标签和蓝色圆圈代表什么？