我们的目标是：

将 $ d(c, v) $ 的表达式代入，对于每条边 $ (p, q) $ 和每个顶点 $ v $，约束变为：

但“至少一个成立”不是线性约束。我们可以将其转化为：对于每个 $ v $，要求 $ d(c, v) \le R $ 等价于要求 $ x $ 必须落在区间 $ [L_v, U_v] $ 之外？不，更准确的方法是，对于固定的边 $ (p, q) $，函数 $ f_v(x) = \min\{A_v + x, B_v - x\} $（其中 $ A_v = d_G(p, v) $, $ B_v = d_G(q, v) + w_{pq} $）是一个分段线性的凹函数（形如“V”形）。要求 $ f_v(x) \le R $ 对所有 $ v $ 成立，等价于寻找 $ x $ 使得所有 $ v $ 对应的“V”形函数都在 $ R $ 以下。这可以通过检查这些线段交点来实现。

因此，树 $ T $ 的直径 $ diam(T) \le 2R^* $。

因此，算法输出的生成树 $ T $ 的直径最多是最优直径 $ D_{opt} $ 的2倍。算法是一个**2-近似算法**。

基于线性规划的图最小直径生成树问题的多项式时间近似算法求解示例 问题描述 在计算机网络、交通规划等领域，我们经常需要设计一个连接所有节点的网络（用生成树表示），使得网络中任意两个节点之间的最远距离（即生成树的 直径 ）尽可能小。这就是 最小直径生成树 （Minimum Diameter Spanning Tree, MDST）问题。 输入 ： 一个无向连通图 \( G = (V, E) \)，其中 \( |V| = n \) 个顶点，\( |E| = m \) 条边。 每条边 \( e = (u, v) \in E \) 有一个非负的长度（或权重） \( w_ {uv} \)。 输出 ： 图 \( G \) 的一棵生成树 \( T \)。 目标 ：最小化这棵生成树的 直径 \( diam(T) \)。生成树的直径定义为树上任意两顶点间最短路径（在树上）长度的最大值，即 \( diam(T) = \max_ {x, y \in V} dist_ T(x, y) \)，其中 \( dist_ T(x, y) \) 是树 \( T \) 上从 \( x \) 到 \( y \) 的唯一路径的长度之和。 这个问题是NP-hard的。然而，我们可以利用线性规划和图论知识，设计一个高效的 2-近似算法 。这意味着算法找到的生成树，其直径最多是最优直径的两倍。本示例将详细讲解这个基于线性规划和 图绝对中心 概念的近似算法。 解题过程详解 我们将算法过程分解为几个逻辑清晰的步骤。 第一步：问题转化与关键洞察 最小直径生成树的核心挑战在于，直径由树上最远的一对点决定。一个关键的数学洞察是： 任何树都有一个或多个 中心 。对于一棵树，其中心是树上的一点（可能是顶点，也可能是某条边内部的点），使得从该点到树上所有点的最远距离最小。这个最小的最远距离称为树的 半径 \( rad(T) \)。对于任何树，都有 \( rad(T) \le diam(T) \le 2 \cdot rad(T) \)。 因此，如果我们能找到图 \( G \) 的一个“中心”点 \( c \)（不一定是顶点），并构建一棵以 \( c \) 为“根”、尽可能使所有顶点都“靠近” \( c \) 的生成树，那么这棵树的半径（从 \( c \) 到最远点的距离）就会较小，根据上述不等式，其直径也会被控制在半径的两倍以内。 这就将问题转化为：在 原图 \( G \) 中找到一个点 \( c \)（称为 绝对1中心 ），使得从 \( c \) 到 \( G \) 中所有顶点的 最短路径距离的最大值 最小化。然后，以此点为中心构造一棵生成树。 第二步：寻找图的绝对1中心（The Absolute 1-Center） 我们不是直接在树上找中心，而是在原图 \( G \) 上找。定义从点 \( c \) 到顶点 \( v \) 的距离 \( d(c, v) \) 为 \( c \) 到 \( v \) 在 原图 \( G \) 中的最短路径长度。 计算全源最短路径 ： 首先，使用Floyd-Warshall算法或多次Dijkstra算法（因为边权非负），计算出原图 \( G \) 中所有顶点对之间的最短路径距离 \( d_ G(u, v) \)。设 \( D \) 为得到的距离矩阵。 建模绝对中心问题 ： 我们要找一个点 \( c \)（可以在顶点上，也可以在边上），最小化 \( \max_ {v \in V} d(c, v) \)。 假设点 \( c \) 位于边 \( (p, q) \in E \) 上。设从端点 \( p \) 到点 \( c \) 的长度为 \( x \)（\( 0 \le x \le w_ {pq} \)），则从端点 \( q \) 到点 \( c \) 的长度为 \( w_ {pq} - x \)。 对于任意顶点 \( v \in V \)，从 \( c \) 到 \( v \) 的最短路径必然要么经过 \( p \)，要么经过 \( q \)，因此： \[ d(c, v) = \min\{ d_ G(p, v) + x, \quad d_ G(q, v) + (w_ {pq} - x) \} \] 我们的目标是： \[ \text{最小化} \quad R \] \[ \text{满足} \quad d(c, v) \le R, \quad \forall v \in V \] 将 \( d(c, v) \) 的表达式代入，对于每条边 \( (p, q) \) 和每个顶点 \( v \)，约束变为： \[ d_ G(p, v) + x \le R \quad \text{和} \quad d_ G(q, v) + w_ {pq} - x \le R \quad \text{至少有一个成立} \] 但“至少一个成立”不是线性约束。我们可以将其转化为：对于每个 \( v \)，要求 \( d(c, v) \le R \) 等价于要求 \( x \) 必须落在区间 \( [ L_ v, U_ v] \) 之外？不，更准确的方法是，对于固定的边 \( (p, q) \)，函数 \( f_ v(x) = \min\{A_ v + x, B_ v - x\} \)（其中 \( A_ v = d_ G(p, v) \), \( B_ v = d_ G(q, v) + w_ {pq} \)）是一个分段线性的凹函数（形如“V”形）。要求 \( f_ v(x) \le R \) 对所有 \( v \) 成立，等价于寻找 \( x \) 使得所有 \( v \) 对应的“V”形函数都在 \( R \) 以下。这可以通过检查这些线段交点来实现。 高效求解算法 ： 不需要解复杂的规划。有一个经典的多项式时间算法可以找到绝对1中心： 候选点 ：图的绝对1中心必然位于某个顶点，或者某条边的某个特定内部点。这个内部点是使“从该点到两个特定顶点的距离相等”的点。 算法步骤 ： a. 对每条边 \( (p, q) \)，考虑所有顶点对 \( (i, j) \)。 b. 在边 \( (p, q) \) 上，可能存在一个点 \( c \)，使得 \( d(c, i) = d(c, j) \) 且这个距离是 \( c \) 到所有顶点的最大距离。这个点 \( c \) 的位置 \( x \) 可以通过解方程 \( A_ i + x = B_ j - x \) 得到，即 \( 2x = B_ j - A_ i \)，所以 \( x = (B_ j - A_ i)/2 \)，其中 \( A_ i = d_ G(p, i) \), \( B_ j = d_ G(q, j) + w_ {pq} \)（注意对称性，也要考虑 \( (j, i) \) 对）。 c. 检查得到的 \( x \) 是否在 \( [ 0, w_ {pq}] \) 区间内。如果在，计算 \( R_ c = A_ i + x \)（或 \( B_ j - x \)）。 d. 同时，图的顶点本身也是候选点。对于每个顶点 \( p \)，计算 \( R_ p = \max_ {v \in V} d_ G(p, v) \)。 从所有候选点（边上的特定点和所有顶点）中，选择使 \( R \) 值最小的那个点 \( c^* \)。这个点 \( c^* \) 就是图的绝对1中心，对应的 \( R^* \) 值称为图的 绝对1中心半径 。注意，这个 \( R^* \) 是 在原图 \( G \) 中从中心点到所有顶点的最短距离的最大值，它是我们能达到的半径的理论下界。 第三步：构造以绝对中心为中心的生成树 现在我们有了中心点 \( c^* \)。如果 \( c^* \) 恰好是一个顶点，构造过程很简单。如果 \( c^* \) 在某条边 \( (p, q) \) 的内部，我们需要构造一棵树，使得 \( c^* \) 在树上“感觉”像是中心。 构建最短路径树 ： 以 \( c^* \) 为源点，在 原图 \( G \) 中运行单源最短路径算法（例如Dijkstra算法）。由于 \( c^* \) 可能在边上，我们可以通过创建两个临时顶点或直接处理距离来模拟。 算法会给出从 \( c^* \) 到每个顶点 \( v \) 的最短路径 \( \pi_ v \) 及其长度 \( d(c^ , v) \)。根据定义，\( \max_ v d(c^ , v) = R^* \)。 合并最短路径形成生成树 ： 考虑所有从 \( c^* \) 到各个顶点 \( v \) 的最短路径 \( \pi_ v \) 的并集。由于 \( c^* \) 是公共起点，这些路径自然构成一个以 \( c^* \) 为根的树形结构（更准确地说，是一个最短路径树）。如果 \( c^* \) 是顶点，这就是标准的最短路径树。如果 \( c^* \) 在边 \( (p, q) \) 上，我们可以想象将边在 \( c^* \) 处“拆分”，将 \( c^* \) 视为一个虚拟的根节点，连接到 \( p \) 和 \( q \)。 这个并集可能不是一棵树（如果有多条等长的最短路径），但我们可以任意选择一条最短路径来构造一棵树 \( T \)。具体地，在Dijkstra算法中，记录每个顶点的“前驱节点”，从而形成一棵以 \( c^* \) 为根的最短路径树 \( T \)。 第四步：算法近似比证明 我们来分析这棵生成树 \( T \) 的直径。 树的半径 ： 在树 \( T \) 上，从中心点 \( c^* \) 到任意顶点 \( v \) 的距离，等于我们在原图 \( G \) 中计算的 \( d(c^ , v) \)。因为 \( T \) 就是由这些最短路径构成的。所以，树 \( T \) 的半径 \( rad(T) = \max_ {v \in V} d_ T(c^ , v) = \max_ {v \in V} d(c^ , v) = R^ \)。 树的直径上界 ： 对于树中的任意两点 \( u \) 和 \( v \)，它们在树 \( T \) 上的距离 \( dist_ T(u, v) \) 满足三角不等式（在树上）： \[ dist_ T(u, v) \le dist_ T(u, c^ ) + dist_ T(c^ , v) = d(c^ , u) + d(c^ , v) \le R^* + R^* = 2R^* \] 因此，树 \( T \) 的直径 \( diam(T) \le 2R^* \)。 与最优解比较 ： 设 \( T_ {opt} \) 是最小直径生成树，其直径为 \( D_ {opt} \)，半径为 \( R_ {opt} \)。根据第一步的不等式，有 \( R_ {opt} \le D_ {opt} \)。 注意，\( R^* \) 是在整个图 \( G \) 中寻找一点到所有顶点最短距离最大值的最小值。而在任何生成树 \( T \) 上，从其中心点 \( c_ T \) 到所有点的距离（在树上的距离）一定 不小于 在 原图 \( G \) 中从同一点到这些点的最短距离。因此，对于最优树 \( T_ {opt} \) 的中心 \( c_ {opt} \)，有 \( R_ {opt} = \max_ {v} dist_ {T_ {opt}}(c_ {opt}, v) \ge \max_ {v} d_ G(c_ {opt}, v) \ge R^* \)。 所以，\( R^* \le R_ {opt} \le D_ {opt} \)。 得到近似比 ： 结合上述结论： \[ diam(T) \le 2R^* \le 2R_ {opt} \le 2D_ {opt} \] 因此，算法输出的生成树 \( T \) 的直径最多是最优直径 \( D_ {opt} \) 的2倍。算法是一个 2-近似算法 。 总结 本算法巧妙地避开了直接求解NP-hard的最小直径生成树问题，而是通过解决一个可以在多项式时间内精确求解的“图绝对1中心”问题，并利用最短路径树构造，得到了一个性能有保证（2倍近似）的生成树。核心步骤是：1) 计算全源最短路径；2) 通过枚举候选点找到图的绝对1中心 \( c^* \)；3) 构建以 \( c^* \) 为根的最短路径树。该算法结合了图论、组合优化和线性规划的思想，是处理网络设计中层优化问题的经典范例。