无向图的最小直径生成树（Minimum Diameter Spanning Tree, MDST）精确算法

问题描述

给定一个无向连通图 \(G = (V, E)\)，边权非负，寻找一棵生成树 \(T\)，使得其直径（任意两点间最短路径的最大长度）最小。这棵生成树称为最小直径生成树（MDST）。

直径定义：树中任意两个顶点间最短路径长度的最大值。

核心思想

MDST问题的关键在于：最小直径生成树的直径中心一定位于某条路径的中点。我们可以利用这个性质，通过枚举所有可能的中点来计算。

详细解题步骤

步骤1：计算全源最短路径

首先使用Floyd-Warshall算法或多次Dijkstra算法，计算图中所有顶点对之间的最短距离：

• 设 \(dist[u][v]\) 表示顶点 \(u\) 到 \(v\) 的最短距离
• 对于 \(n\) 个顶点的图，时间复杂度为 \(O(n^3)\)（Floyd-Warshall）或 \(O(n(m+n\log n))\)（多次Dijkstra）

步骤2：理解中心概念

对于树中的一条路径 \(P = (v_1, v_2, ..., v_k)\)：

• 直径长度 \(D = \sum_{i=1}^{k-1} w(v_i, v_{i+1})\)
• 该路径的中心可以是一个顶点，也可以是边的中点

关键观察：最小直径生成树必然存在一条直径路径，其中心（顶点或边的中点）是整棵树的绝对中心。

步骤3：绝对中心理论

绝对中心是一个点 \(x\)（可能在边上），使得距离它最远的顶点距离最小：

\[ \text{最小直径} = 2 \times \min_{x} \max_{v \in V} d(x, v) \]

设绝对中心位于边 \((u,v)\) 上，距离 \(u\) 为 \(\alpha\)，距离 \(v\) 为 \(w(u,v)-\alpha\)（\(0 \leq \alpha \leq w(u,v)\)）。

步骤4：枚举边的算法

1. 预处理排序：
   对于每条边 \((u,v)\)，考虑所有顶点 \(z\)：
   定义 \(f_u(z) = dist[u][z]\)，\(f_v(z) = dist[v][z]\)
   按 \(f_u(z) - f_v(z)\) 的差值对顶点排序

2. 计算候选中心：
   对于边 \((u,v)\)，定义函数：

\[ g(\alpha) = \max_{z \in V} \min(f_u(z) + \alpha, f_v(z) + w(u,v) - \alpha) \]

这个函数是若干线性函数的上包络，其最小值点可以通过检查顶点顺序变化的位置找到。

3. 具体步骤：
   a. 对边 \((u,v)\)，将顶点按 \(f_u(z) - f_v(z)\) 降序排列
   b. 初始时，\(\alpha = 0\)，最远顶点是使 \(f_u(z)\) 最大的顶点
   c. 随着 \(\alpha\) 增加，最远顶点会发生变化。变化点发生在：

\[ f_u(z_i) + \alpha = f_v(z_j) + w(u,v) - \alpha \]

d. 计算所有变化点处的 \(g(\alpha)\)，取最小值

4. 算法复杂度：
   • 每条边需要 \(O(n \log n)\) 排序
   • 共 \(m\) 条边，总复杂度 \(O(mn \log n)\)

步骤5：从绝对中心构造MDST

找到绝对中心 \(x\) 后，构造MDST：

1. 如果中心在顶点 \(c\)：

   • 以 \(c\) 为根，建立最短路径树
   • 对每个顶点 \(v\)，选择使 \(dist[c][v]\) 最小的边加入

2. 如果中心在边 \((u,v)\) 上，距 \(u\) 为 \(\alpha\)：

   • 引入虚拟顶点 \(c\)，连接 \(c-u\) 权值 \(\alpha\)，\(c-v\) 权值 \(w(u,v)-\alpha\)
   • 以 \(c\) 为根，为每个顶点选择最短路径
   • 移除虚拟顶点 \(c\)，得到生成树

步骤6：算法流程总结

1. 计算全源最短路径 \(dist[\cdot][\cdot]\)
2. 初始化最佳直径 \(d_{best} = \infty\)，最佳中心 \(center\)
3. 对每个顶点 \(u\)：
   • 计算 \(\max_{v} dist[u][v]\)，如果 \(< d_{best}\)，更新
4. 对每条边 \((u,v)\) 权值 \(w\)：
   • 对顶点按 \(dist[u][z] - dist[v][z]\) 排序
   • 扫描排序列表，计算函数 \(g(\alpha)\) 的最小值
   • 如果 \(2 \times \min g(\alpha) < d_{best}\)，更新最佳直径和中心
5. 根据最佳中心构造MDST
6. 返回MDST及其直径

步骤7：实例演示

考虑一个4顶点正方形图：

A---1---B
|       |
2       3
|       |
C---4---D

边权：AB=1, BD=3, DC=4, CA=2, AD=?

1. 计算全源最短路径（略）
2. 检查顶点中心：
   • 以A为中心的最大距离：max(dist[A][B]=1, dist[A][D]=?, ...)
3. 检查边中心：
   • 对边AB，计算 \(g(\alpha)\) 的最小值
4. 最终找到绝对中心，构造MDST

算法复杂度分析

• 全源最短路径：\(O(n^3)\) 或 \(O(n(m+n\log n))\)
• 枚举所有边：\(O(mn \log n)\)
• 总复杂度：\(O(n^3 + mn \log n)\)（使用Floyd-Warshall）

扩展与应用

1. 近似算法：如果不需要精确解，可以简单取图的中心顶点构建最短路径树
2. 加权版本：顶点有权重时，需要加权距离
3. 动态维护：当图动态变化时，MDST需要重新计算

这个算法巧妙地利用了图的度量性质，通过寻找绝对中心来最小化树的直径，是图论中几何与组合性质结合的典型例子。