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

题目描述

最短路径树（Shortest Path Tree, SPT）是图论中的一个重要概念。给定一个带权有向图（或无向图）和一个源点，我们的目标是从源点出发，到达所有可达顶点，并且所经过的路径是“最短的”。更具体地说，最短路径树是原图的一棵生成树（以源点为根），它满足：从源点到树上任意一个顶点的唯一路径，就是原图中从源点到该顶点的最短路径。

本题目要求：给定一个带非负权边的有向图和一个源点，使用 Dijkstra 算法构建出从该源点出发的最短路径树，并讲解其实现细节、正确性原理以及如何从算法的结果中复原出这棵树。

循序渐进讲解

步骤1：理解最短路径树与单源最短路径的关系

首先，我们需要理清几个概念：

• 单源最短路径（SSSP）： 计算从一个特定源点 s 到图中所有其他顶点的最短距离。
• 最短路径树（SPT）： 这是 SSSP 问题的一个“副产品”或“具体体现”。它不仅给出了最短距离，还指明了如何通过一棵树（一种无环的子图）来达到这些最短距离。在这棵树中，从根 s 到任意节点 v 的路径，就是原图中 s 到 v 的一条实际的最短路径。

关键洞察： 对于同一个源点，最短路径可能不唯一。因此，最短路径树也可能不唯一。但任何一棵合法的 SPT 都能给出正确的最短距离。

步骤2：回顾 Dijkstra 算法——获取最短距离

由于题目限定边权非负，我们使用经典的 Dijkstra 算法。我们来回顾其计算最短距离的核心过程：

1. 初始化：

   • 创建一个距离数组 dist[]，dist[s] = 0，其他顶点 dist[v] = ∞。
   • 创建一个优先队列（最小堆）pq，初始放入 (0, s)，表示从源点 s 出发，当前已知最短距离为 0。
   • 创建一个集合（或布尔数组）visited，记录哪些顶点的最短距离已被最终确定。

2. 主循环：

   • 当 pq 非空时，弹出当前距离最小的顶点 u。
   • 如果 u 已被访问过（visited[u] = true），则跳过（这是处理优先队列中同一顶点旧数据的关键）。
   • 标记 u 为已访问 (visited[u] = true)。此时，dist[u] 的值就是源点 s 到 u 的最终最短距离。 这是 Dijkstra 算法的核心性质：当从优先队列中弹出某个顶点时，它的距离已经是最优的。
   • 松弛操作：遍历 u 的所有邻接边 (u, v, weight)。如果通过 u 到 v 能得到更短的路径，即 dist[u] + weight < dist[v]，则：
     • 更新 dist[v] = dist[u] + weight。
     • 将 (dist[v], v) 压入优先队列 pq。

这个循环结束后，dist[] 数组就存储了从源点 s 到所有顶点的最短距离。

步骤3：扩展 Dijkstra 算法——记录前驱以构建路径树

为了构建最短路径树，而不仅仅是知道距离，我们需要在松弛操作时，记录下“是谁更新了我”。这通过一个 前驱数组（predecessor array） prev[] 来实现。

• 初始化： prev[v] = -1 或 null，表示暂无前驱。prev[s] 可以设为 s 自身或一个特殊值（如 -1），表示它是根。
• 修改松弛操作：

  if dist[u] + weight < dist[v]:
      dist[v] = dist[u] + weight
      prev[v] = u  // 关键！记录 v 在当前最短路径上的前一个顶点是 u
      将 (dist[v], v) 压入 pq
  

• 逻辑解释： 当发现通过顶点 u 到达 v 是一条更短的路径时，我们不仅更新距离，还“记住”了这条更优路径的最后一步是从 u 过来的。因此，u 成为了 v 在当前找到的最短路径上的前驱。

步骤4：从 prev[] 数组复原最短路径树

算法结束后，prev[] 数组定义了一棵以源点 s 为根的树（或森林，对于不可达的顶点，其 prev 值为初始值）。

• 对于任意一个可达的顶点 v (prev[v] != -1)，从 v 开始，不断查找其前驱：v -> prev[v] -> prev[prev[v]] -> ...，最终一定会回溯到源点 s。这条逆向路径反过来，就是从 s 到 v 的最短路径。
• 所有顶点及其对应的 prev 关系，构成了最短路径树的有向边。即，对于每个 v != s 且 prev[v] != -1，存在一条树边 (prev[v] -> v)，其权重就是原图中这条边的权重。

步骤5：算法示例

考虑下图，源点为 A。

    (A) --4--> (B)
     |        ^  |
     2        1  5
     v   6   |  v
    (C) --- (D) <-- (E)
             3

我们手动模拟算法，重点关注 prev[] 的变化。

1. 初始化: dist[A]=0, 其他为 ∞。prev 全为 -1。pq = [(0, A)]。
2. 弹出 A (dist=0)：
   • 松弛 A->B: dist[B]=0+4=4, prev[B]=A, pq加入(4,B)。
   • 松弛 A->C: dist[C]=0+2=2, prev[C]=A, pq加入(2,C)。
3. 弹出 C (dist=2)：
   • 松弛 C->D: dist[D]=2+6=8, prev[D]=C, pq加入(8,D)。
4. 弹出 B (dist=4)：
   • 松弛 B->D: 4+5=9 > 8，不更新。
   • 松弛 B->E: dist[E]=4+3=7, prev[E]=B, pq加入(7,E)。
5. 弹出 E (dist=7)：
   • 松弛 E->D: 7+1=8 等于当前dist[D]=8，注意：根据典型Dijkstra，此时不更新，因为距离相等。这意味着存在另一条等长最短路径 A->C->D。我们通常约定，当距离相等时，保持先找到的前驱（这里是C），或根据问题要求选择。这里我们保持C。所以 prev[D] 仍为 C。
6. 弹出 D (dist=8)：其出边不影响已确定顶点。
7. 队列空，结束。

最终结果：

• dist: A:0, B:4, C:2, D:8, E:7
• prev: A:-1, B:A, C:A, D:C, E:B
• 最短路径树（SPT）的边为：(A->B), (A->C), (C->D), (B->E)。
• 验证：从A到D的最短路径是 A->C->D，距离 2+6=8，与 dist[D] 一致，且树中也体现了这条路径。

步骤6：实现细节与复杂度

• 数据结构：
  • dist[]: 一维数组。
  • prev[]: 一维数组。
  • visited[] 或使用 dist 比较来替代（如果当前弹出的顶点距离大于 dist[u]，说明是旧数据，跳过）。
  • 优先队列：通常用二叉堆，存储 (distance, vertex) 对。
• 时间复杂度：
  • 与标准 Dijkstra 相同，取决于优先队列的实现。使用二叉堆为 O((V+E) log V)，其中 V 是顶点数，E 是边数。
• 空间复杂度： O(V+E) 用于存储图，O(V) 用于 dist, prev 等数组。

总结

构建最短路径树的核心在于，在运行 Dijkstra 算法求解最短距离的同时，利用一个 prev 数组记录下每次成功松弛时的前驱顶点。算法结束后，prev 数组天然地定义了一棵树（或森林），树中的每条边对应原图中的一条边，并且从根（源点）到任意树节点的路径，恰好是原图中对应的一条最短路径。这个 prev 数组就是最短路径树的紧凑表示，通过它可以方便地重构出任一顶点的具体最短路径。