为什么 Dijkstra 算法在目标标签 7 首次出现时不立即将其最终确定？

适用条件

• 图正在由 Dijkstra 算法处理。
• 带有圈出标签的顶点被视为已选定/已确定。
• 未圈出的标签仍是暂定候选值。
• 存在至少一个未圈出的顶点，其标签小于目标的当前标签。

理解与推导

1. 识别目标处的当前候选标签（大学 = 7）。
2. 扫描所有未圈出的顶点以获取其暂定标签。
3. 找到最小的未圈出标签（$E = 4$）。
4. 将最小的未圈出标签与目标标签进行比较（$4 < 7$）。
5. 得出结论：目标标签还不能最终确定，因为还有更小的候选值未确定。
6. 处理较小的顶点（E），看看它是否能改善目标标签。

例子

在视频中，演示者明确指出：“现在，我们不能仅仅断定七一定是最短距离，因为我们还有其他顶点需要考虑。所以最小的未圈出顶点是这里的另一个四。” 顶点 E（标签为 4）在大学处的标签 7 最终确定之前被圈出。

容易误解的地方

• 错误地将第一个目标标签视为一旦出现即为最终值。
• 假设单条可见路线已经证明了最优性，而没有检查其他未确定的分支。
• 认为算法一旦到达目标就终止，而不是当目标是未圈出的最小顶点时才终止。

观看对应讲解

继续追问

• 在找到距离后，如何恢复实际的最短路径？
• 在这个算法演示中，写在顶点处的数字代表什么？
• 为什么在处理目标之前要先处理顶点 E？