如何验证带权有向图中生成树T是否为根s的最短路径树？

问题描述 #

给定带权有向图 (G(V, E))（边权非负）、根顶点 (s \in V)，以及一棵以 (s) 为根的生成树 (T(V, E'))（(E' \subseteq E)），需要设计时间复杂度为 (O(V+E)) 的算法，验证 (T) 是否为 (G) 中以 (s) 为根的最短路径树。

解决方案 #

核心判定逻辑 #

一棵生成树是最短路径树的充要条件有两个：

1. 树中从 (s) 到每个顶点 (v) 的路径长度，等于图 (G) 中 (s) 到 (v) 的最短距离；
2. 对于图中任意边 ((u, v))，满足三角不等式 (d(v) \leq d(u) + w(u, v))（(w(u, v)) 为边的权重），确保不存在通过非树边构造的更短路径。

基于此，我们可以设计线性时间的验证流程：

具体步骤 #

• 区分树边与非树边
  遍历图 (G) 的所有边，用哈希表或邻接表标记出不属于生成树 (T) 的边（非树边），无需修改树结构，时间复杂度 (O(E))。

• 计算生成树内的节点距离 (d_T(v))
  以 (s) 为根，通过DFS或BFS遍历生成树 (T)，计算每个节点 (v) 从 (s) 出发的路径长度：

  • 初始化 (d_T(s) = 0)；
  • 对每个节点 (u)，遍历其在 (T) 中的子节点 (v)，设置 (d_T(v) = d_T(u) + w(u, v))。
    这一步仅需遍历树的 (V-1) 条边，时间复杂度 (O(V))。

• 计算图的全局最短距离 (d(v))
  利用边权非负的特性，通过拓扑排序+松弛操作线性时间计算 (s) 到所有节点的最短距离：

  • 初始化 (d(s) = 0)，其余节点 (d(v) = +\infty)；
  • 对图 (G) 进行拓扑排序；
  • 按拓扑顺序依次对每个节点 (u) 的邻接边 ((u, v)) 执行松弛：若 (d(v) > d(u) + w(u, v))，则更新 (d(v))。
    时间复杂度 (O(V+E))。

• 双重验证

  1. 检查所有节点 (v) 是否满足 (d_T(v) = d(v))：确保树中路径是最短路径，时间复杂度 (O(V))；
  2. 检查所有边 ((u, v)) 是否满足 (d(v) \leq d(u) + w(u, v))：确保不存在更短的替代路径，时间复杂度 (O(E))。

时间复杂度总结 #

所有步骤的总时间复杂度为 (O(V+E))，符合线性时间要求。

补充说明 #

若仅验证非树边的三角不等式，可能会忽略生成树本身路径不是最短的情况（比如树中某条边的路径长度大于全局最短距离）。因此必须同时完成上述两项验证，才能确保 (T) 是最短路径树。

内容的提问来源于stack exchange，提问作者Orkhan Aliyev