Dijkstra算法如何精确重建最短路径？

一、前置：prev数组的核心作用 #

在Dijkstra算法执行过程中，prev数组（或字典）是路径重建的关键。它的每个元素prev[v]存储的是从起点到节点v的最短路径中，v的前一个节点。算法运行时，只有当通过当前节点到达邻居的距离，比邻居当前记录的最短距离更小时，才会更新邻居的prev值——这一步是路径正确性的核心，并非简单存入节点。

二、具体重建步骤 #

假设已完成Dijkstra算法计算，得到起点start到目标节点end的最短距离，以及完整的prev数组，重建路径的过程如下：

1. 初始化路径容器：创建空列表（或栈）存储路径，先将目标节点end加入其中。
2. 回溯遍历prev数组：从end开始，不断查找prev[当前节点]，将找到的节点加入路径，直到遍历到起点start（起点的prev通常设为None或自身，作为终止标志）。
   比如prev[end] = u，prev[u] = w，prev[w] = start，回溯顺序为end → u → w → start。
3. 反转路径得到正序：将回溯得到的逆序路径反转，最终得到从起点到终点的正序最短路径。

三、实际例子说明 #

假设存在图：起点A，连接关系为A→B（权重2）、A→C（权重5）、B→D（权重1）、C→D（权重3）。

• 算法执行后prev数组内容：prev[B] = A，prev[C] = A，prev[D] = B。
• 重建到D的路径：
  1. 加入D → [D]
  2. 找prev[D]得到B，加入 → [D, B]
  3. 找prev[B]得到A，加入 → [D, B, A]
  4. 反转后得到正序路径：[A, B, D]，对应总权重3，是最短路径。

四、易混淆的细节 #

• prev数组的更新是条件触发：只有发现更短路径时才会修改邻居的prev值，并非每次访问节点都更新。
• 多最短路径场景：若存在多条长度相同的最短路径，prev数组只会记录其中一条（取决于算法遍历邻居的顺序），但按步骤回溯仍能得到有效最短路径。

内容的提问来源于stack exchange，提问作者1440p