

最小直径生成树

在学习最小直径生成树（Minimum Diameter Spanning Tree）前建议先阅读树的直径的内容。

在无向图的所有生成树中，直径最小的那一棵生成树就是最小直径生成树。

图的绝对中心¶

求解直径最小生成树，首先需要找到 图的绝对中心 ， 图的绝对中心 可以存在于一条边上或某个结点上，该中心到所有点的最短距离的最大值最小。

根据 图的绝对中心 的定义可以知道，到绝对中心距离最远的结点至少有两个。

令 d[i][j] 为顶点间的最短路径长，通过多源最短路算法求出所有结点的最短路。

rk[i][j] 记录点到其他所有结点中第小的那个结点。

图的绝对中心可能在某条边上，枚举每一条边，并且假设图的绝对中心就在这条边上。那么距离的长度为 ( )，距离的长度就是。

对于图中的任意一点，图的绝对中心到的距离为。

举例一个结点，该结点与图的绝对中心的位置关系如下图。

mdst1

随着图的绝对中心在边上的改变会生成一个距离与位置的函数图像。显然的，当前的的函数图像是一个两条斜率相同的线段构成的折线段。

mdst2

对于图上的任意一结点，图的绝对中心到最远距离结点的函数就写作，其函数图像如下。

mdst3

并且这些折线交点中的最低点，横坐标就是图的绝对中心的位置。

图的绝对中心可能在某个结点上，用距离预选结点最远的那个结点来更新，即。

算法流程¶

使用多源最短路算法（ Floyd ， Johnson 等），求出数组；
求出 rk[i][j] ，并将其升序排序；
图的绝对中心可能在某个结点上，用距离预选结点最远的那个结点来更新，遍历所有结点并用更新最小值。
图的绝对中心可能在某条边上，枚举所有的边。对于一条边从距离最远的结点开始更新。当出现的情况时，用来更新。因为这种情况会使图的绝对中心改变。

参考实现

bool cmp(int a, int b) { return val[a] < val[b]; }

void Floyd() {
  for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

void solve() {
  Floyd();
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      rk[i][j] = j;
      val[j] = d[i][j];
    }
    sort(rk[i] + 1, rk[i] + 1 + n, cmp);
  }
  int ans = INF;
  // 图的绝对中心可能在结点上
  for (int i = 1; i <= n; i++) ans = min(ans, d[i][rk[i][n]] * 2);
  // 图的绝对中心可能在边上
  for (int i = 1; i <= m; i++) {
    int u = a[i].u, v = a[i].v, w = a[i].w;
    for (int p = n, i = n - 1; i >= 1; i--) {
      if (d[v][rk[u][i]] > d[v][rk[u][p]]) {
        ans = min(ans, d[u][rk[u][i]] + d[v][rk[u][p]] + w);
        p = i;
      }
    }
  }
}