运行 Dijkstra 算法后，如何重建从家到大学的最短路径？

适用条件

• 在前驱箭头必须在标签更新期间被记录下来。
• 目标标签已经最终确定（被圈出）。
• 图是有向的，或者为了遵循记录的箭头而被视为有向的。

理解与推导

1. 从目标顶点（大学）开始。
2. 识别指向大学的的前驱箭头（来自 D）。
3. 移动到顶点 D。
4. 识别指向 D 的前驱箭头（来自 A）。
5. 移动到顶点 A。
6. 识别指向 A 的前驱箭头（来自家）。
7. 移动到源顶点（家）。
8. 反转序列以向前顺序陈述路径：家 → $A \to D$ → 大学。

例子

视频显示黄色高亮追踪向后路线：“从大学向后工作，我们来自 D …… 从 D 向后跟随箭头，它来自 A …… 然后从 A 跟随，它来自家。” 最终路径写为 家 - A - D - 大学。

容易误解的地方

• 假设路径是通过从源向前跟随箭头找到的。
• 忘记在算法期间记录前驱箭头，使得重建不可能。
• 将最短距离值与实际顶点序列混淆。

观看对应讲解

继续追问

• 在这个例子中，从家到大学的最终最短距离是多少？
• 图图中的蓝色箭头代表什么？
• 如何计算最短路径的总距离？