def get_path(parent, v):
    path = []
    while v != -1: # 一直回溯到源点 s（其 parent 为 -1）
        path.append(v)
        v = parent[v]
    return path[::-1] # 反转列表，得到从 s 到 v 的路径

        (B)
       4/ \1
      (A) (C)
       2\ /3
        (D)

        (B)
        /
      (A)
        \
        (D)
          \
          (C)

最短路径树（Shortest Path Tree, SPT）的构建算法 题目描述 给定一个带权有向图（或无向图）和一个源点 s ，我们的目标是构建一棵 最短路径树（Shortest Path Tree, SPT） 。 什么是 最短路径树 ？ 它是从源点 s 出发，到达图中所有 可达顶点 的一棵有根树。这棵树满足一个核心性质： 树上从源点 s 到任意可达顶点 v 的路径，恰好是原图中从 s 到 v 的 一条 最短路径 。 请注意，从源点到某个顶点的最短路径可能不止一条。最短路径树就是从所有可能的最短路径中，选出一组，使它们整体构成一棵树（每个顶点在树中只出现一次，且没有环）。 任务： 详细讲解如何利用 Dijkstra 算法 （针对非负权图）来构建这样一棵最短路径树。 解题过程：使用 Dijkstra 算法构建 SPT 我们将过程分解为几个清晰的步骤。 第一步：理解核心数据结构与算法输入 图表示 ：我们假设图使用邻接表表示。对于每个顶点 u ，我们存储一个列表，包含其邻居顶点 v 以及边的权重 w(u, v) 。 源点 ：指定一个顶点 s 作为树的根。 算法需要维护的信息 ： dist[v] ：记录当前从源点 s 到顶点 v 的 最短距离估计值 。初始化时， dist[s] = 0 ，其他所有顶点的 dist 为无穷大（∞）。 parent[v] ：这是构建 SPT 的关键 。它记录在当前的“最佳路径”中，顶点 v 是从哪个顶点过来的（即 v 在路径树上的父节点）。初始化时，所有 parent 为 NULL 或 -1 。 visited 集合（或 Priority Queue ）：用于高效地选取下一个要处理的顶点。 第二步：Dijkstra 算法流程与 SPT 的构建 Dijkstra 算法是一个 贪心算法 。它的核心思想是，每次从未确定最短路径的顶点中，选择一个距离源点 最近 的顶点，并“确定”它的最短距离，然后通过它来更新其邻居的距离。 我们将详细说明每一步如何同时更新 dist 和 parent 数组，最终形成 SPT。 初始化 ： 创建 dist 数组和 parent 数组。 设置 dist[s] = 0 。 设置 parent[s] = -1 （源点没有父节点，它是根）。 将所有顶点（除 s 外）的 dist 设为 ∞， parent 设为 -1 。 使用一个 最小优先队列（Min-Heap） ，初始时将源点 s 和它的距离 0 放入队列。队列按 dist 值排序。 主循环 （当优先队列不为空时）： a. 提取最近顶点 ：从优先队列中取出 dist 值最小的顶点，记为 u 。此时， dist[u] 的值就是 s 到 u 的最终最短距离。我们称顶点 u 被“确定”或“访问”。 b. 松弛操作（Relaxation）与父节点更新 ：遍历顶点 u 的所有邻居 v 及其边权 w 。 * 计算新路径长度 ： newDist = dist[u] + w(u, v) 。 * 判断与更新 ： 如果 newDist < dist[v] ，说明我们找到了一条从 s 到 v 的更短路径，这条路径是 经过 u 的。 * 更新 dist[v] = newDist 。 * 关键步骤 ：更新 parent[v] = u 。这意味着，在当前找到的最佳路径中， v 应该连接在 u 之后。 * 将 v 连同其新的 dist[v] 加入或更新到优先队列中（如果使用可减少键值的堆，则进行减键操作；否则直接插入新记录，旧的记录会在被取出时因 dist 值更大而被忽略）。 循环终止 ：当优先队列为空时，算法结束。此时： dist[v] 存储了从 s 到 v 的最短路径长度（若为 ∞ 则表示不可达）。 parent[v] 数组则定义了一棵树—— 最短路径树（SPT） 。 第三步：如何从 parent 数组还原出 SPT 和具体路径 算法结束后， parent 数组本身就代表了这棵 SPT。 这棵树的根是 s 。 对于任意一个顶点 v （ v != s 且 dist[v] != ∞ ）， parent[v] 就是它在 SPT 中的父节点。 边集 { (parent[v], v) | 对于所有 v，满足 parent[v] != -1 } 就构成了最短路径树的所有边。 如何找到从 s 到 v 的具体最短路径？ 从顶点 v 开始，反复查找 parent 数组，直到回溯到源点 s ，将沿途的顶点逆序输出即可。 第四步：实例演示 考虑下图（无向图，但算法对有向图同样适用），源点为 A 。 邻接表： A: (B,4), (D,2) B: (A,4), (C,1) C: (B,1), (D,3) D: (A,2), (C,3) 我们模拟 Dijkstra 算法构建 SPT 的过程： | 步骤 | 从队列取出的顶点 u (dist[ u]) | 更新操作与 parent 变化 | 更新后的 dist (parent) | | :--- | :---------------------------- | :------------------------------------------ | :------------------- | | 初始 | - | dist[ A]=0, parent[ A ]=-1; 其他为 ∞(-1) | A:0(-1), B:∞(-1), C:∞(-1), D:∞(-1) | | 1 | A (0) | 看邻居 B: new=0+4=4 < ∞，更新。 parent[B]=A 看邻居 D: new=0+2=2 < ∞，更新。 parent[D]=A | A:0(-1), B:4(A), C:∞(-1), D:2(A) | | 2 | D (2) | 邻居 A: 已确定，跳过。 邻居 C: new=2+3=5 < ∞，更新。 parent[C]=D | A:0(-1), B:4(A), C:5(D), D:2(A) | | 3 | B (4) | 邻居 A: 已确定，跳过。 邻居 C: new=4+1=5 等于 dist[ C]=5，不更新（或更新但不改变 parent，取决于实现）。通常，如果距离相等，我们选择最先找到的那条路径的父节点（即保持 parent[ C ]=D）。 | A:0(-1), B:4(A), C:5(D), D:2(A) | | 4 | C (5) | 邻居 B, D: 都已确定，无更新。队列为空，结束。 | | 最终 parent 数组： parent[A] = -1 (根) parent[B] = A parent[C] = D parent[D] = A 这定义了一棵最短路径树（SPT）： 边为： (A, B) , (A, D) , (D, C) 。 验证路径： A->B: 路径 A-B，距离 4。 A->C: 路径 A-D-C，距离 5。 A->D: 路径 A-D，距离 2。 总结 通过 Dijkstra 算法 构建最短路径树的关键在于，在标准的距离松弛操作中， 同步维护一个 parent 数组 。每当因为发现一条更短的路径而更新某个顶点 v 的 dist[v] 时，就将 v 的父节点 parent[v] 设置为当前正在处理的顶点 u 。算法结束时， parent 数组就编码了一棵以 s 为根的最短路径树，它包含了从源点出发到所有可达顶点的某一条最短路径。