AIOJ

Before studying the Minimum Diameter Spanning Tree, it is recommended to read Tree Diameter first.

Definition

Among all spanning trees of an undirected graph, the one with the smallest diameter is the minimum diameter spanning tree.

Absolute Center of a Graph

To find a minimum diameter spanning tree, we first need to find the absolute center of the graph. The absolute center of a graph may lie on an edge or at a vertex; it is the center that minimizes the maximum of its shortest-path distances to all vertices.

By the definition of the absolute center of a graph, at least two vertices are farthest from the absolute center.

Let $d(i,j)$ be the shortest-path length between vertices $i,j$ . Use a multi-source shortest-path algorithm to compute the shortest paths between all vertices.

$\textit{rk}(i,j)$ records the vertex that is the $j$ -th closest among all vertices to vertex $i$ .

The absolute center of the graph may lie on an edge. Enumerate every edge $w=(u,v)$ and assume that the absolute center $c$ lies on this edge. Let its distance from $u$ be $x$ ( $x \leq w$ ), so its distance from $v$ is $w - x$ .

For any vertex $i$ in the graph, the distance from the absolute center $c$ to $i$ is $d(c,i)=\min(d(u,i) + x, d(v,i) + (w - x))$ .

For example, consider a vertex $i$ and its positional relationship with the absolute center of the graph, as shown below.

mdst1

As the absolute center $c$ moves along the edge, it gives a function of distance versus the position of $c$ . Clearly, the graph of the current $d(c,i)$ is a broken line made of two line segments with the same slope.

mdst2

For any vertex in the graph, the function giving the distance from the absolute center to the farthest vertex is written as $f = \max\{ d(c,i)\},i \in[1,n]$ , whose graph is shown below.

mdst3

The lowest point among the intersections of these broken lines has an x-coordinate equal to the position of the absolute center.

The absolute center may be at a vertex. Update the answer using the vertex farthest from that vertex, namely $\textit{ans}\leftarrow \min(\textit{ans},d(i,\textit{rk}(i,n))\times 2)$ .

Procedure

Use a multi-source shortest-path algorithm (Floyd, Johnson, etc.) to compute the $d$ array；
Compute $\textit{rk}(i,j)$ and sort it in ascending order；
The absolute center may be at a vertex. Update the minimum by iterating over all vertices and using $\textit{ans}\leftarrow \min(\textit{ans},d(i,\textit{rk}(i,n)) \times 2)$ with the vertex farthest from each vertex；
The absolute center may lie on an edge, so enumerate all edges. For an edge $w(u,v)$ , start updating from the vertex farthest from $u$ . When $d(v,\textit{rk}(u,i)) > \max_{j=i+1}^n d(v,\textit{rk}(u,j))$ , update with $\textit{ans}\leftarrow \min(\textit{ans}, d(u,\textit{rk}(u,i))+\max_{j=i+1}^n d(v,\textit{rk}(u,j))+w(u,v))$ . This situation changes the position of the absolute center.

Implementation

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;
  // The absolute center of the graph may be at a vertex
  for (int i = 1; i <= n; i++) ans = min(ans, d[i][rk[i][n]] * 2);
  // The absolute center of the graph may lie on an edge
  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;
      }
    }
  }
}

Example

CodeForce 266D BerDonalds

Minimum Diameter Spanning Tree

From the definition of the absolute center of a graph, it is easy to see that the absolute center is the midpoint of the diameter of a minimum diameter spanning tree.

To find a minimum diameter spanning tree, first find the absolute center of the graph. Starting from the absolute center, construct a shortest-path tree; this gives a minimum diameter spanning tree.

Implementation

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;
constexpr int MAXN = 502;
using ll = long long;
using pii = pair<int, int>;
ll d[MAXN][MAXN], dd[MAXN][MAXN], rk[MAXN][MAXN], val[MAXN];
constexpr ll INF = 1e17;
int n, m;

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]);
}

struct node {
  ll u, v, w;
} a[MAXN * (MAXN - 1) / 2];

void solve() {
  // Find the absolute center of the graph
  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);
  }
  ll P = 0, ansP = INF;
  // At a vertex
  for (int i = 1; i <= n; i++) {
    if (d[i][rk[i][n]] * 2 < ansP) {
      ansP = d[i][rk[i][n]] * 2;
      P = i;
    }
  }
  // On an edge
  int f1 = 0, f2 = 0;
  ll disu = INT_MIN, disv = INT_MIN, ansL = INF;
  for (int i = 1; i <= m; i++) {
    ll 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]]) {
        if (d[u][rk[u][i]] + d[v][rk[u][p]] + w < ansL) {
          ansL = d[u][rk[u][i]] + d[v][rk[u][p]] + w;
          f1 = u, f2 = v;
          disu = (d[u][rk[u][i]] + d[v][rk[u][p]] + w) / 2 - d[u][rk[u][i]];
          disv = w - disu;
        }
        p = i;
      }
    }
  }
  cout << min(ansP, ansL) / 2 << '\n';
  // Minimum spanning tree
  vector<pii> pp;
  for (int i = 1; i <= 501; ++i)
    for (int j = 1; j <= 501; ++j) dd[i][j] = INF;
  for (int i = 1; i <= 501; ++i) dd[i][i] = 0;
  if (ansP <= ansL) {
    for (int j = 1; j <= n; j++) {
      for (int i = 1; i <= m; ++i) {
        ll u = a[i].u, v = a[i].v, w = a[i].w;
        if (dd[P][u] + w == d[P][v] && dd[P][u] + w < dd[P][v]) {
          dd[P][v] = dd[P][u] + w;
          pp.push_back({u, v});
        }
        u = a[i].v, v = a[i].u, w = a[i].w;
        if (dd[P][u] + w == d[P][v] && dd[P][u] + w < dd[P][v]) {
          dd[P][v] = dd[P][u] + w;
          pp.push_back({u, v});
        }
      }
    }
    for (auto [x, y] : pp) cout << x << ' ' << y << '\n';
  } else {
    d[n + 1][f1] = disu;
    d[f1][n + 1] = disu;
    d[n + 1][f2] = disv;
    d[f2][n + 1] = disv;
    a[m + 1].u = n + 1, a[m + 1].v = f1, a[m + 1].w = disu;
    a[m + 2].u = n + 1, a[m + 2].v = f2, a[m + 2].w = disv;
    n += 1;
    m += 2;
    floyd();
    P = n;
    for (int j = 1; j <= n; j++) {
      for (int i = 1; i <= m; ++i) {
        ll u = a[i].u, v = a[i].v, w = a[i].w;
        if (dd[P][u] + w == d[P][v] && dd[P][u] + w < dd[P][v]) {
          dd[P][v] = dd[P][u] + w;
          pp.push_back({u, v});
        }
        u = a[i].v, v = a[i].u, w = a[i].w;
        if (dd[P][u] + w == d[P][v] && dd[P][u] + w < dd[P][v]) {
          dd[P][v] = dd[P][u] + w;
          pp.push_back({u, v});
        }
      }
    }
    cout << f1 << ' ' << f2 << '\n';
    for (auto [x, y] : pp)
      if (x != n && y != n) cout << x << ' ' << y << '\n';
  }
}

void init() {
  for (int i = 1; i <= 501; ++i)
    for (int j = 1; j <= 501; ++j) d[i][j] = INF;
  for (int i = 1; i <= 501; ++i) d[i][i] = 0;
}

int main() {
  init();
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    ll u, v, w;
    cin >> u >> v >> w;
    w *= 2;
    d[u][v] = w, d[v][u] = w;
    a[i].u = u, a[i].v = v, a[i].w = w;
  }
  solve();
  return 0;
}

Examples

SPOJ MDST

timus 1569. Networking the "Iset"

SPOJ PT07C - The GbAaY Kingdom

References

Play with Trees Solutions The GbAaY Kingdom