↩ back to Minimum Spanning Trees
The site's tenth Minimum Spanning Trees entry isn't an eleventh way to build the same spanning tree, and it isn't a different question about the same fixed vertex set the way Minimum Bottleneck Spanning Tree and Second-Best Spanning Tree are — it relaxes which vertices even have to show up. A Steiner tree connects only a required subset of a graph's nodes (the terminals), free to route through any of the rest (Steiner points) as unpriced waypoints if that happens to be cheaper than connecting the terminals directly. Every ordinary minimum spanning tree is a Steiner tree where every node happens to be a terminal; the general problem — some nodes required, the rest optional — is NP-hard, with no known polynomial algorithm that always finds the true minimum. What is polynomial, and what this page actually builds and verifies, is the classic guaranteed-within-2× approximation: treat the terminals as a small complete graph weighted by shortest-path distance in the original graph, and reuse Kruskal's algorithm — this site's own minimum-spanning-tree builder — on that instead.
A telecom operator needs to run cable connecting three towns — Fairview, Bristol, and Cedar Falls. Two more sites on the map, Junction 1 and Junction 2, need no service of their own — they're only useful as places the cable is allowed to pass through. None of the three towns has a cheap direct line to another; the inexpensive routes all run through the junctions. Switch between the three approaches below to see the same eight candidate cable segments used three different ways.
Shortest-path distance in a weighted graph always satisfies the triangle inequality —
dist(u, w) ≤ dist(u, v) + dist(v, w) — since any detour through v is itself a
valid u-to-w path, so the true shortest path can never be longer. That's the only
fact this approximation needs. Let T* be some optimal Steiner tree connecting the k
terminals (using whichever Steiner points it needs), with total weight OPT. Walk a depth-first tour
around T* that traverses every edge exactly twice — once down, once back up — for a total
walk length of exactly 2·OPT. That closed walk visits every terminal at least once; reading off the
terminals in the order the walk first reaches each one produces a cycle touching all k of
them, and by the triangle inequality the shortest-path distance between consecutive terminals in that
order is never more than the portion of the doubled walk between those two visits — so the whole cycle
of shortest-path hops costs at most 2·OPT too. Dropping the cycle's single most expensive hop leaves a
path touching all k terminals — a spanning tree of the terminals' own complete graph of
pairwise shortest-path distances — at a cost still at most 2·OPT. A minimum spanning tree of that same
complete graph can only cost less than or equal to any one spanning tree of it, so weight(MST on
terminal metric closure) ≤ 2·OPT follows immediately. The last step is just bookkeeping: turning
each abstract shortest-path edge back into its real path in the original graph and taking the union
can only remove weight, never add it, whenever two chosen paths happen to share a real edge — so the
actual materialized tree this page builds is never heavier than the metric-closure MST that bounded it.
Two applications of "can only get cheaper, never more expensive" — cycle to path, abstract MST to real
tree — is the entire proof.
The bound is tight only in the worst case; nothing here claims the approximation usually gets within a hair of 2×. On this page's own five-site network the ratio it actually measures is 8 / 7 ≈ 1.14 — comfortably inside the guarantee, and typical of how loose the bound is in practice on graphs with real structure rather than an adversarially constructed one.
Three pieces: a plain single-source Dijkstra (reused once per terminal, not once — the same function Dijkstra's algorithm's own page builds), the abstract Kruskal step over the terminals' complete graph, and the materialize-and-dedupe pass that turns the abstract answer back into real edges:
function dijkstraFrom(src, numNodes, adj) {
const dist = new Array(numNodes).fill(Infinity);
const prevEdge = new Array(numNodes).fill(null);
const visited = new Array(numNodes).fill(false);
dist[src] = 0;
for (let step = 0; step < numNodes; step++) {
let u = -1, best = Infinity;
for (let i = 0; i < numNodes; i++) if (!visited[i] && dist[i] < best) { best = dist[i]; u = i; }
if (u === -1) break;
visited[u] = true;
for (const e of adj[u]) {
if (dist[u] + e.w < dist[e.to]) { dist[e.to] = dist[u] + e.w; prevEdge[e.to] = { from: u, edge: e.edge }; }
}
}
return { dist, prevEdge };
}
function steinerApprox(numNodes, adj, allEdges, terminals) {
// One Dijkstra per terminal — this is the only place the algorithm looks at the whole graph.
const shortest = terminals.map(t => dijkstraFrom(t, numNodes, adj));
// The terminals' own complete graph, weighted by shortest-path distance.
const virtualEdges = [];
for (let i = 0; i < terminals.length; i++) {
for (let j = i + 1; j < terminals.length; j++) {
virtualEdges.push({ i, j, a: terminals[i], b: terminals[j], w: shortest[i].dist[terminals[j]] });
}
}
// Kruskal, exactly as kruskal.html's own reference implementation runs it — just on
// terminals-and-distances instead of the original graph's own nodes-and-edges.
virtualEdges.sort((x, y) => x.w - y.w);
const parent = {};
terminals.forEach(t => parent[t] = t);
function find(x) { while (parent[x] !== x) x = parent[x] = parent[parent[x]]; return x; }
const chosenVirtual = [];
for (const e of virtualEdges) {
const ra = find(e.a), rb = find(e.b);
if (ra !== rb) { parent[ra] = rb; chosenVirtual.push(e); }
}
// Materialize each chosen virtual edge into its real shortest path, then dedupe: two
// different terminal pairs can share a real segment of road.
const seen = new Set();
const realEdges = [];
for (const ve of chosenVirtual) {
let cur = terminals[ve.j];
while (cur !== terminals[ve.i]) {
const pe = shortest[ve.i].prevEdge[cur];
const key = pe.edge.a < pe.edge.b ? pe.edge.a + '-' + pe.edge.b : pe.edge.b + '-' + pe.edge.a;
if (!seen.has(key)) { seen.add(key); realEdges.push(pe.edge); }
cur = pe.from;
}
}
return { chosenVirtual, realEdges, weight: realEdges.reduce((s, e) => s + e.w, 0) };
}The demo's "true optimal" mode is not this algorithm — it's a brute-force oracle that tries every subset of the optional Steiner points, runs an ordinary MST over terminals-plus-that-subset for each, and keeps the cheapest connected result. That's exponential in the number of optional nodes and only exists on this page to check the approximation against a known-correct answer on a network small enough to afford it (2 optional nodes, 4 subsets) — it isn't a general algorithm anyone should reach for beyond a handful of Steiner points.
Skipping the Steiner points entirely doesn't just cost more — it can fail to connect the
terminals at all. Running plain Kruskal on only the three towns' own direct edges, ignoring
both junctions, finds exactly one usable edge (Fairview–Cedar Falls, weight 20) and stops: Bristol has
no direct edge to either other town, so it's left completely isolated. The result isn't a worse Steiner
tree, it's not a tree over the required terminals at all — nothing crashes, and a caller that only
checks "did Kruskal return without error" would never notice Bristol was dropped. Verified against the
real shipped script's "terminals only" mode: it reports connected: false and a tree
missing one of the three required towns, not merely a heavier one.
Materializing each terminal pair's shortest path independently can miss a shared connector
that a smarter combined route would reuse. The true optimum on this page's own network
(weight 7) routes Fairview and Bristol both through Junction 1, then crosses to Junction 2 over the
cheap direct Junction 1–Junction 2 link (weight 1) to reach Cedar Falls — one connector serving both
remaining hops at once. The approximation's per-pair view never considers that link at all: Fairview–
Bristol's own shortest path (weight 4, via Junction 1) and Bristol–Cedar Falls's own shortest path
(weight 4, via Junction 2) are each individually optimal for that one pair, but the Junction 1–Junction
2 edge never appears on either point-to-point shortest path, since routing through both junctions is
never the shortest way between any single pair of towns — only across all three at once. The
materialized result (weight 8) is still a valid, still within-bound answer, just not the true minimum;
verified against the real shipped script by comparing its own realEdges to the
brute-force oracle's tree and confirming neither shares the Junction 1–Junction 2 edge.
Time: O(k · E log V) for k Dijkstra runs, one per terminal
(a binary-heap implementation would reach this; this page's own array-based Dijkstra, like
Dijkstra's algorithm's own reference implementation, is
O(k · V²) instead, "for simplicity of the code shown, not simplicity of the real cost,"
the same tradeoff Prim's algorithm makes). Building and sorting the
terminals' complete graph is O(k² log k); materializing and deduping the chosen paths
back into real edges is O(k · V) worst case. For k small relative to the graph —
the usual case, since terminals are typically a handful of required sites in a much larger network —
the k Dijkstra runs dominate.
Space: O(V + E) for the graph plus O(k²) for the terminals'
own complete graph. The brute-force optimal oracle this page uses only for verification is a different
story entirely: O(2^m) in the number of optional Steiner points m, since it tries
every subset — the exact reason the general Steiner Tree Problem is NP-hard and this page doesn't
attempt an exact algorithm for graphs of any real size.
For a decision guide across all ten of this site's Minimum Spanning Trees entries — including where a genuinely different question like this one fits — see Choosing a Minimum Spanning Tree Algorithm.