最小直径生成树问题 题目描述 给定一个无向连通图G=(V, E)，其中每条边具有非负权重。目标是找到图G的一棵生成树T，使得T的直径最小。生成树的直径定义为树中所有顶点对之间的最短路径的最大值，即任意两顶点间距离的最大值。 解题过程 问题理解 最小直径生成树（MDST）问题要求在所有生成树中，选择那棵“最紧凑”的树，即树中距离最远的两个顶点之间的距离（直径）尽可能小。与最小生成树（MST）不同，MDST不关注边权重之和，而是关注拓扑结构上的紧凑性。 关键观察 图的绝对中心（Absolute 1-Center）定理：存在一个顶点或边上的点c，使得c到所有顶点的最短距离的最大值（偏心距）最小。这个最小偏心距称为图的半径。 MDST的直径等于2倍图的半径（如果中心在边上，可能需要调整）。因此，问题转化为寻找图的绝对中心，并以该中心为根构造最短路径树。 算法步骤（基于绝对中心的方法） 步骤1：计算所有顶点对之间的最短路径 使用Floyd-Warshall算法或|V|次Dijkstra算法，得到距离矩阵D，其中D[ i][ j ]表示顶点i到j的最短距离。 目的：为后续计算绝对中心提供全局距离信息。 步骤2：寻找图的绝对中心 绝对中心可以是顶点或边上的任意点。对于每条边(u, v)，权重为w，考虑边上的点x，其到u的距离为α（0≤α≤w），到v的距离为w-α。 对于每个顶点k，定义函数f_ k(α) = min(D[ u][ k] + α, D[ v][ k ] + w - α)，表示点x到顶点k的距离。 边(u, v)上所有函数f_ k(α)的上包络（最大值函数）F(α) = max_ {k∈V} f_ k(α)，表示点x的偏心距。 求F(α)在α∈[ 0, w ]上的最小值，即为该边上的最小偏心距。遍历所有边，取全局最小偏心距对应的点作为绝对中心c。 实操：可通过计算函数交点找到F(α)的最小值点。 步骤3：以绝对中心为根构造最短路径树 若中心c是顶点，直接以c为源点，运行Dijkstra算法，得到的最短路径树即为MDST。 若中心c在边(u, v)上，将c视为临时顶点，分别计算c到u和v的最短路径（通过边(u, v)），再以c为源点运行Dijkstra算法（需适当调整图结构）。 验证：该树的直径恰好等于2倍最小偏心距，且是全局最优解。 复杂度分析 步骤1：Floyd-Warshall为O(|V|³)或|V|次Dijkstra为O(|V|² log |V|)（基于堆优化）。 步骤2：遍历|E|条边，每条边处理|V|个函数，整体O(|V||E|)。 步骤3：单次Dijkstra为O(|E| log |V|)。 总复杂度以O(|V|³)或O(|V|² log |V|)为主，适用于中小规模图。 示例说明 考虑一个4顶点图：边(u,v)=2, (u,w)=5, (v,w)=3, (w,x)=1。 计算距离矩阵后，发现边(v,w)上存在一个点c，到各顶点距离的最大值为2.5（最小偏心距）。 以c为根构造树：c连接v和w，w连接x，v连接u，直径=5（u到x路径），满足最小直径。