Steiner Tree Problem

Minimum spanning tree vs Steiner tree — adding Steiner points reduces total length

7
200

Click canvas to add terminals. Right-click to remove the nearest one.

MST edges Steiner tree edges Steiner points Terminal nodes
—MST length
—Steiner length
—Savings %
About: The Steiner tree problem asks for the shortest network connecting a set of terminals, allowing extra "Steiner points" to be added. Unlike the Minimum Spanning Tree (which only uses terminals), Steiner points can reduce total length by up to ~13.4% (the Steiner ratio for Euclidean space, proven by Chung & Graham 1985 to be √3/2). The exact Steiner tree is NP-hard for general graphs, but the Euclidean Steiner problem can be solved approximately by iterative relaxation (Melzak's algorithm). All Steiner points have exactly 3 edges meeting at 120° angles.