在 Dijkstra 算法期间，如何处理单个顶点处的多个距离值？

适用条件

• 顶点可以通过来自不同圈出顶点的多条路径到达。
• 对已标记的顶点执行新的距离计算。

理解与推导

1. 从当前圈出的顶点计算到该顶点的新暂定距离。
2. 将这个新距离与该顶点处的现有标签进行比较。
3. 如果新距离更小，用新标签替换旧标签并更新前驱箭头。
4. 如果新距离更大或相等，划掉新值并保留现有的较小标签。
5. 继续选择下一个最小的未圈出顶点。

例子

在视频中，顶点 C 最初有一个来自家的标签 3。当从 A 处理时，计算出新距离 $4 (2 + 2)$。因为 $4 > 3$，值 4 被划掉，3 保留为 C 的有效距离。演讲者说：“每当我们在一个顶点处有两个或更多数字时，我们将划掉任何不等于最小值的数字。”

容易误解的地方

• 在单个顶点处留下多个距离值，导致混乱。
• 用较大的值更新标签。
• 忘记划掉较大的值，这可能会在后来被错误地选中。

观看对应讲解

继续追问

• 在 Dijkstra 算法演示中，顶点处的数字标签和蓝色圆圈代表什么？
• 为什么 Dijkstra 算法在目标标签 7 首次出现时不立即将其最终确定？
• 运行 Dijkstra 算法后，如何重建从家到大学的最短路径？