Calculator inputs
Use graph mode for exact small weighted networks. Use Euclidean mode for three terminal points in the plane.
Example data table
| Scenario | Input | Expected insight |
|---|---|---|
| Graph sample | Edges: A-B 3, A-D 2, D-E 2, E-F 2, F-G 2, B-C 4. Terminals: A, C, G. | The exact solver may use non-terminal connectors such as D, E, or F. |
| Euclidean sample | A(0,0), B(6,0), C(3,5) | An interior Steiner point usually lowers length below the terminal MST. |
| Degenerate Euclidean case | A(0,0), B(8,0), C(1,0.2) | If one angle reaches 120° or more, no interior Steiner point is needed. |
Formula used
Graph metric case: the calculator solves the exact small Steiner tree problem with Dreyfus-Wagner dynamic programming on shortest-path distances.
DP[S, v] = min( min(DP[A, v] + DP[S\A, v]), min(DP[S, u] + d(u, v)) )
Here, S is a subset of terminal indices, v is a graph node, and d(u, v) is the all-pairs shortest-path distance.
Terminal-only comparison: the savings figure compares the exact Steiner tree against an MST built on the metric closure of terminal distances.
Euclidean three-terminal case: if every triangle angle is below 120°, the optimal point is the Fermat point, found numerically here by minimizing:
f(x, y) = |SA| + |SB| + |SC|
If any angle is at least 120°, the optimal tree connects that vertex directly to the other two points.
How to use this calculator
- Choose graph mode for weighted networks or Euclidean mode for three points.
- In graph mode, enter one undirected edge per line using comma-separated values.
- List the terminal nodes you want the tree to connect.
- In Euclidean mode, enter coordinates for points A, B, and C.
- Press Solve Steiner Tree to place the result above the form.
- Review total cost, selected connectors, and savings versus terminal-only spanning structure.
- Use the CSV or PDF buttons to export the result table.
Frequently asked questions
1. What does this calculator solve exactly?
It solves an exact small graph Steiner tree problem and a specialized Euclidean three-terminal case. Both versions estimate the shortest connection network that links required terminals with optional connectors.
2. Why can the graph solver use non-terminal nodes?
Steiner trees are allowed to include helpful intermediate nodes. Those extra nodes can shorten the total connection length compared with linking terminals alone through a spanning tree.
3. Is the graph answer exact or approximate?
For the stated small-size limits, the graph mode is exact. It uses dynamic programming on shortest-path distances and reconstructs the chosen tree edges afterward.
4. Why does Euclidean mode only accept three points?
The classic three-terminal Euclidean case has a clean geometric structure involving the Fermat point or a 120° angle condition. Larger Euclidean Steiner problems are much harder to solve exactly.
5. What does the savings value mean?
Savings equals terminal MST cost minus Steiner tree cost. A positive value means optional Steiner nodes or an interior Steiner point reduce the total required connection length.
6. What happens when one Euclidean angle is at least 120°?
No interior Steiner point is needed. The minimal tree simply joins that wide-angle vertex directly to the other two terminals.
7. Why are there size limits in graph mode?
Exact Steiner tree computation grows quickly with the number of terminals and nodes. The limit keeps the page practical while still supporting advanced small-network analysis.
8. Can I use decimal edge weights and coordinates?
Yes. The solver accepts decimal values for graph weights and Euclidean coordinates, then reports results with six decimal places for consistency.