最小直径生成树
在学习最小直径生成树（Minimum Diameter Spanning Tree）前建议先阅读 树的直径 的内容．
定义
在无向图的所有生成树中，直径最小的那一棵生成树就是最小直径生成树．
图的绝对中心
求解直径最小生成树，首先需要找到 图的绝对中心 ，图的绝对中心 可以存在于一条边上或某个结点上，该中心到所有点的最短距离的最大值最小．
根据 图的绝对中心 的定义可以知道，到绝对中心距离最远的结点至少有两个．
令 𝑑(𝑖,𝑗)d(i,j)
为顶点 𝑖,𝑗i,j 间的最短路径长，通过多源最短路算法求出所有结点的最短路．
𝑟𝑘(𝑖,𝑗)rk(i,j) 记录点 𝑖i 到其他所有结点中第 𝑗j 小的那个结点．
图的绝对中心可能在某条边上，枚举每一条边 𝑤 =(𝑢,𝑣)w=(u,v)，并且假设图的绝对中心 𝑐c 就在这条边上．那么距离 𝑢u 的长度为 𝑥x（𝑥 ≤𝑤x≤w），距离 𝑣v 的长度就是 𝑤 −𝑥w−x．
对于图中的任意一点 𝑖i，图的绝对中心 𝑐c 到 𝑖i 的距离为 𝑑(𝑐,𝑖) =min(𝑑(𝑢,𝑖) +𝑥,𝑑(𝑣,𝑖) +(𝑤 −𝑥))d(c,i)=min(d(u,i)+x,d(v,i)+(w−x))．
举例一个结点 𝑖i，该结点与图的绝对中心的位置关系如下图．
随着图的绝对中心 𝑐c 在边上的改变会生成一个距离与 𝑐c 位置的函数图像．显然的，当前的 𝑑(𝑐,𝑖)d(c,i) 的函数图像是一个两条斜率相同的线段构成的折线段．
对于图上的任意一结点，图的绝对中心到最远距离结点的函数就写作 𝑓 =max{𝑑(𝑐,𝑖)},𝑖 ∈[1,𝑛]f=max{d(c,i)},i∈[1,n]，其函数图像如下．
并且这些折线交点中的最低点，横坐标就是图的绝对中心的位置．
图的绝对中心可能在某个结点上，用距离预选结点最远的那个结点来更新，即 𝑎𝑛𝑠 ←min(𝑎𝑛𝑠,𝑑(𝑖,𝑟𝑘(𝑖,𝑛)) ×2)ans←min(ans,d(i,rk(i,n))×2)．
过程
- 求出 𝑟𝑘(𝑖,𝑗)rk(i,j)，并将其升序排序；
- 图的绝对中心可能在某个结点上，用距离预选结点最远的那个结点来更新，遍历所有结点并用 𝑎𝑛𝑠 ←min(𝑎𝑛𝑠,𝑑(𝑖,𝑟𝑘(𝑖,𝑛)) ×2)ans←min(ans,d(i,rk(i,n))×2) 更新最小值．
- 图的绝对中心可能在某条边上，枚举所有的边．对于一条边 𝑤(𝑢,𝑣)w(u,v) 从距离 𝑢u 最远的结点开始更新．当出现 𝑑(𝑣,𝑟𝑘(𝑢,𝑖)) >max𝑛𝑗=𝑖+1𝑑(𝑣,𝑟𝑘(𝑢,𝑗))d(v,rk(u,i))>maxj=i+1nd(v,rk(u,j)) 的情况时，用 𝑎𝑛𝑠 ←min(𝑎𝑛𝑠,𝑑(𝑢,𝑟𝑘(𝑢,𝑖)) +max𝑛𝑗=𝑖+1𝑑(𝑣,𝑟𝑘(𝑢,𝑗)) +𝑤(𝑢,𝑣))ans←min(ans,d(u,rk(u,i))+maxj=i+1nd(v,rk(u,j))+w(u,v)) 来更新．因为这种情况会使图的绝对中心改变．
实现
---|---
### 例题
* [CodeForce 266D BerDonalds](https://codeforces.com/contest/266/problem/D)
## 最小直径生成树
根据图的绝对中心的定义，容易得知图的绝对中心是最小直径生成树的直径的中点．
求解最小直径生成树首先需要找到图的绝对中心．以图的绝对中心为起点，生成一个最短路径树，那么就可以得到最小直径生成树了．
实现
---|---
例题
timus 1569. Networking the "Iset"
SPOJ PT07C - The GbAaY Kingdom
参考文献
Play with Trees Solutions The GbAaY Kingdom
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：ShaoChenHeng, Enter-tainer, StudyingFather, Tiphereth-A, Alisahhh, billchenchina, Early0v0, iamtwz, Ir1d, ksyx, leoleoasd, Marcythm, mcendu, opsiff, ouuan, Suiseiseki-2016, TrisolarisHD, wplf 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用