最短路径树（Shortest Path Tree, SPT）的构建算法

题目描述

给定一个带权有向图（或无向图）和一个源顶点，计算从该源顶点到图中所有其他顶点的最短路径。但本题不仅要求输出最短距离，还要求构造出以源顶点为根的一棵“最短路径树”。在这棵树中，从根到任意树中顶点的唯一路径，就是原图中从源点到该顶点的最短路径。
本质上，这需要我们在执行经典最短路径算法（如 Dijkstra 或 Bellman-Ford）的同时，记录下每条最短路径的前驱节点，最终通过前驱关系还原出一棵树（或森林，如果图不连通）。

预备知识

• 最短路径：图中从源点 s 到目标点 t 的路径，其所有边的权重之和最小。
• 前驱数组：prev[v] 表示在计算出的最短路径上，顶点 v 的前一个顶点是谁。如果从 s 到 v 有多条最短路径，通常约定其中一条。

解题过程

我们以 Dijkstra 算法为例，因为它是无负权边时最高效的单源最短路径算法，并且能自然导出一棵最短路径树。

第一步：理解算法输出

Dijkstra 算法的标准形式是，给定图 G=(V, E) 和源点 s，计算数组 dist[]，其中 dist[v] 是从 s 到 v 的最短距离。
为了构建最短路径树，我们增加一个数组 prev[]（或 parent[]）。在算法更新最短距离时，如果发现通过某个中间顶点 u 到 v 能得到更短的 dist[v]，我们就同时设置 prev[v] = u。这意味着“在当前找到的最短路径中，v 的前一个是 u”。

第二步：算法初始化

• 设顶点集为 V，边集为 E，权重函数为 w(e) >= 0。
• 创建数组 dist[|V|]，初始化 dist[s] = 0，其他为 ∞。
• 创建数组 prev[|V|]，初始化所有项为 NULL（或 -1），表示尚未找到前驱。
• 创建一个优先队列（最小堆）Q，将所有顶点按 dist 值插入。或者，可以只插入源点，随后在松弛时插入新顶点。

第三步：主循环与松弛操作

Dijkstra 的主循环从 Q 中取出当前 dist 最小的顶点 u，然后检查它的每条出边 (u, v)，进行“松弛”操作：

如果 dist[u] + w(u, v) < dist[v]：
    dist[v] = dist[u] + w(u, v)  # 更新最短距离
    prev[v] = u                   # 更新前驱
    更新 v 在优先队列中的 dist 值（或重新插入）

这个松弛操作的实质是：如果我们发现经过 u 到 v 比之前已知的任何路径都短，那么当前最短路径中 v 就应该从 u 过来。

第四步：构建最短路径树

当算法结束时：

• dist[v] 就是从 s 到 v 的最短距离（如果 dist[v] 仍为 ∞，表示 v 不可达）。
• 对于每个可达的顶点 v（v ≠ s），prev[v] 指向的顶点是它在最短路径上的直接前驱。
• 所有这样的前驱关系 (prev[v], v) 构成了一棵以 s 为根的有向树（在无向图中，树是无向的，但前驱关系仍定义了方向）。
  注意：如果原图是连通的，这棵树会包含所有顶点；如果不连通，则得到一片最短路径森林（每个连通分量有一棵以该分量中源点可达的顶点为根的树）。

第五步：验证与理解

为什么这样能形成一棵树？
因为对每个顶点（除了源点），prev[v] 唯一确定了一个“父节点”，且沿着前驱指针回溯，最终一定会到达源点 s（否则就会出现环，这与最短路径的最优子结构矛盾）。
另外，树中从 s 到 v 的路径长度等于 dist[v]，这正是 Dijkstra 算法所保证的。

例子

考虑下图（有向，权重已标）：

顶点: 0, 1, 2, 3
边: 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5)
源点 s = 0

运行 Dijkstra 并记录 prev：

1. 初始：dist=[0, ∞, ∞, ∞], prev=[null, null, null, null]
2. 取出 0，松弛边：dist[1]=4, prev[1]=0；dist[2]=1, prev[2]=0
3. 取出 2（dist=1），松弛边：经 2→1 得新距离 1+2=3<4，故更新 dist[1]=3, prev[1]=2；经 2→3 得 dist[3]=1+5=6, prev[3]=2
4. 取出 1（dist=3），松弛边：经 1→3 得新距离 3+1=4<6，故更新 dist[3]=4, prev[3]=1
5. 取出 3，结束。

最终 prev 数组：prev[0]=null, prev[1]=2, prev[2]=0, prev[3]=1。
最短路径树（有向边）为：0→2, 2→1, 1→3。
验证：从 0 到 3 的最短路径 0→2→1→3 长度 1+2+1=4，等于 dist[3]。

复杂度

• 时间复杂度：与 Dijkstra 相同，使用二叉堆时为 O((V+E) log V)，使用斐波那契堆可降至 O(V log V + E)。
• 空间复杂度：O(V) 存储 dist 和 prev 数组。

注意事项

1. 如果图中存在零权边，算法依然正确。
2. 如果存在负权边，Dijkstra 不适用，应使用 Bellman-Ford 算法，并同样记录 prev 数组。但需注意，当存在负权环时，最短路径可能不存在，Bellman-Ford 能检测出这种情况，此时最短路径树没有定义。
3. 当有多条最短路径时，prev 数组只会记录其中一条（取决于松弛顺序），因此最短路径树不唯一。如果需要所有最短路径，则需记录多个前驱。

通过以上步骤，你可以在求解单源最短路径的同时，得到一棵具体的最短路径树，它在网络路由、图形绘制等领域有直接应用。