Steiner Tree

The Steiner tree problem is a combinatorial optimization problem, similar to the minimum spanning tree, and is a type of shortest network. The minimum spanning tree seeks the shortest network connecting all points within a given set of points and edges. In contrast, the minimum Steiner tree allows the addition of extra points beyond the given set to minimize the cost of the generated shortest network.

Problem Introduction

In the early 19^th century, the renowned geometer Steiner from the University of Berlin studied a very simple yet insightful problem: connecting three villages with roads of minimal total length. Mathematically, given three points \(A\), \(B\), and \(C\) in the plane, find a fourth point \(P\) such that the sum \(a+b+c\) is minimized, where \(a\), \(b\), and \(c\) represent the distances from \(P\) to \(A\), \(B\), and \(C\), respectively.

The answer to the problem is: If every interior angle of triangle \(\textit{ABC}\) is less than \(120^{\circ}\), then \(P\) is the point where the angles subtended by edges \(\textit{AB}\), \(\textit{BC}\), and \(\textit{AC}\) are all \(120^{\circ}\). If one angle of triangle \(\textit{ABC}\), say angle \(C\), is greater than or equal to \(120^{\circ}\), then point \(P\) coincides with vertex \(C\).

Problem Generalization

1. In the Steiner problem, three fixed points \(A,B,C\) are given. Naturally, this problem can be generalized to the case of \(n\) given points \(A_1,A_2,\dots,A_n\); we seek a point \(P\) in the plane such that the sum of distances \(a_1+a_2+\dots+a_n\) is minimized, where \(a_i\) is the distance \(PA_i\).

2. Considering other relevant factors of the points, weights are introduced. The other relevant factors of the \(n\) points can be converted into weights, and we seek a point \(P\) in the plane such that the weighted sum \(a_1\cdot w_1+a_2\cdot w_2+\dots+a_n\cdot w_n\) is minimized, where \(w_i\) is the weight of each point.

3. The first generalization proposed by Courant and Robbins is superficial. To obtain a truly valuable generalization of the Steiner problem, we must abandon the search for a single point \(P\) and instead consider a "road network" with the shortest total length. Mathematically, given \(n\) points \(A_1,A_2,\cdots,A_n\), we seek a system of straight line segments connecting these \(n\) points with the shortest total length, such that any two points can be connected by a polyline composed of the segments in the system. They termed this new problem the Steiner tree problem. In the case of \(n\) given points, there can be at most \(n-2\) junction points (Steiner points). At each Steiner point, at most three edges meet. If three edges meet, they pairwise intersect at angles of \(120^{\circ}\); if two edges meet, then this Steiner point must coincide with one of the given points, and the angle between the two edges must be greater than or equal to \(120^{\circ}\).

Shortest network connecting more than three points

In the first case, the solution consists of five line segments, with two Steiner points (red \(s_1,s_2\)) where three segments meet and intersect at angles of \(120^{\circ}\). The solution in the second case contains three Steiner points. In the third case, one or more Steiner points may degenerate or be replaced by one or more given points.

We present the Steiner tree problem model in graph-theoretic form.

For form one, if we let the key points be \(\{1,2,3,4\}\), we can see that directly connecting these four key points yields a minimum edge weight sum of 12, which is clearly not optimal. If node 5 is considered, the minimum edge weight sum becomes 9, yielding a better answer.

For form two, if we let the key points be \(\{1,2,3,4\}\), we can see that some of these key points do not even have directly connecting edges, so junction points (Steiner points) must be considered. Including node 5 gives a minimum edge weight sum of 9.

Moreover, we can observe that in both graphs, the Steiner points for nodes 1 and 4 are degenerate and are replaced by nodes 1 or 4.

Example Problems

First, let's use a template problem to familiarize everyone with the minimum Steiner tree problem. See 【Template】Minimum Steiner Tree.

The problem statement is clear: given \(n\) points and \(k\) key points in a connected graph \(G\), connect the \(k\) key points such that the sum of all edge weights in the generated tree is minimized.

Based on the above knowledge, we know that directly connecting these \(k\) key points may not yield the minimum weight sum, or these \(k\) key points may not be directly (adjacently) connected. Therefore, the remaining \(n-k\) points should be utilized.

We use state compression dynamic programming to solve this. Let \(f(i,S)\) denote the minimum edge weight sum of a tree rooted at \(i\) that contains all points in set \(S\).

Consider state transitions:

• First, transition over connected subsets: \(f(i,S)\leftarrow \min(f(i,S),f(i,T)+f(i,S-T))\).

• Perform edge relaxation under the current connected subset state: \(f(i,S)\leftarrow \min(f(i,S),f(j,S)+w(j,i))\). In the code below, a tree[tot] is used to record information about two connected nodes \(i,j\).

Reference Implementation

#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

constexpr int MAXN = 510;
constexpr int INF = 0x3f3f3f3f;
using P = pair<int, int>;
int n, m, k;

struct edge {
  int to, next, w;
} e[MAXN << 1];

int head[MAXN << 1], tree[MAXN << 1], tot;
int dp[MAXN][5000], vis[MAXN];
int key[MAXN];
priority_queue<P, vector<P>, greater<P>> q;

void add(int u, int v, int w) {
  e[++tot] = edge{v, head[u], w};
  head[u] = tot;
}

void dijkstra(int s) {  // Solve the shortest path
  memset(vis, 0, sizeof(vis));
  while (!q.empty()) {
    P item = q.top();
    q.pop();
    if (vis[item.second]) continue;
    vis[item.second] = 1;
    for (int i = head[item.second]; i; i = e[i].next) {
      if (dp[tree[i]][s] > dp[item.second][s] + e[i].w) {
        dp[tree[i]][s] = dp[item.second][s] + e[i].w;
        q.push(P(dp[tree[i]][s], tree[i]));
      }
    }
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  memset(dp, INF, sizeof(dp));
  cin >> n >> m >> k;
  int u, v, w;
  for (int i = 1; i <= m; i++) {
    cin >> u >> v >> w;
    add(u, v, w);
    tree[tot] = v;
    add(v, u, w);
    tree[tot] = u;
  }
  for (int i = 1; i <= k; i++) {
    cin >> key[i];
    dp[key[i]][1 << (i - 1)] = 0;
  }
  for (int s = 1; s < (1 << k); s++) {
    for (int i = 1; i <= n; i++) {
      for (int subs = s & (s - 1); subs;
           subs = s & (subs - 1))  // Bitmask DP, refer to the detailed explanation in the solution
        dp[i][s] = min(dp[i][s], dp[i][subs] + dp[i][s ^ subs]);
      if (dp[i][s] != INF) q.push(P(dp[i][s], i));
    }
    dijkstra(s);
  }
  cout << dp[key[1]][(1 << k) - 1] << '\n';
  return 0;
}

Another classic example is [WC2008] Tour Plan.

This problem asks for the Steiner tree with the minimum vertex weight sum. Let \(f(i,S)\) denote the minimum vertex weight sum of a tree rooted at \(i\) that contains all points in set \(S\). \(a_i\) represents the vertex weight.

Consider state transitions:

• \(f(i,S)\leftarrow \min(f(i,S),f(i,T)+f(i,S-T)-a_i)\). Since the same point \(a_i\) is added twice during merging, we subtract it once.

• \(f(i,S)\leftarrow \min(f(i,S),f(j,S)+w(j,i))\).

It can be observed that the state transitions are similar to those in the template problem above. The challenge lies in outputting the answer, as we also need to record paths during DP.

Use pre[i][s] to record the point and set information when transitioning to a tree rooted at \(i\) with connected state set \(s\). After DP, start from pre[root][S] and search for points connected to those in the set, gradually decomposing set \(S\). Use an ans array to record the points used. When the set is fully decomposed, the search ends.

Reference Implementation

#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

#define mp make_pair
using P = pair<int, int>;
using PP = pair<P, int>;
constexpr int INF = 0x3f3f3f3f;
constexpr int dx[] = {0, 0, -1, 1};
constexpr int dy[] = {1, -1, 0, 0};
int n, m, K, root;
int f[101][1111], a[101], ans[11][11];
bool inq[101];
PP pre[101][1111];
queue<P> q;

bool legal(P u) {
  if (u.first >= 0 && u.second >= 0 && u.first < n && u.second < m) {
    return true;
  }
  return false;
}

int num(P u) { return u.first * m + u.second; }

void spfa(int s) {
  memset(inq, 0, sizeof(inq));
  while (!q.empty()) {
    P u = q.front();
    q.pop();
    inq[num(u)] = false;
    for (int d = 0; d < 4; d++) {
      P v = mp(u.first + dx[d], u.second + dy[d]);
      int du = num(u), dv = num(v);
      if (legal(v) && f[dv][s] > f[du][s] + a[dv]) {
        f[dv][s] = f[du][s] + a[dv];
        if (!inq[dv]) {
          inq[dv] = true;
          q.push(v);
        }
        pre[dv][s] = mp(u, s);
      }
    }
  }
}

void dfs(P u, int s) {
  if (!pre[num(u)][s].second) return;
  ans[u.first][u.second] = 1;
  int nu = num(u);
  if (pre[nu][s].first == u)
    dfs(u, s ^ pre[nu][s].second);  // Find the answer via dfs
  dfs(pre[nu][s].first, pre[nu][s].second);
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  memset(f, INF, sizeof(f));
  cin >> n >> m;
  int tot = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> a[tot];
      if (!a[tot]) {
        f[tot][1 << (K++)] = 0;
        root = tot;
      }
      tot++;
    }
  }
  for (int s = 1; s < (1 << K); s++) {
    for (int i = 0; i < n * m; i++) {
      for (int subs = s & (s - 1); subs; subs = s & (subs - 1)) {
        if (f[i][s] > f[i][subs] + f[i][s ^ subs] - a[i]) {
          f[i][s] = f[i][subs] + f[i][s ^ subs] - a[i];  // State transition
          pre[i][s] = mp(mp(i / m, i % m), subs);
        }
      }
      if (f[i][s] < INF) q.push(mp(i / m, i % m));
    }
    spfa(s);
  }
  cout << f[root][(1 << K) - 1] << '\n';
  dfs(mp(root / m, root % m), (1 << K) - 1);
  for (int i = 0, tot = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (!a[tot++])
        cout << 'x';
      else
        cout << (ans[i][j] ? 'o' : '_');
    }
    if (i != n - 1) cout << '\n';
  }
  return 0;
}

Exercises

• 【Template】Minimum Steiner Tree
• [WC2008] Tour Plan
• [JLOI2015] Pipeline Connection
• [APIO2013] Robots

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用