Given an undirected weighted graph G = (V, E) and an integer s that partitions the set of vertices V = [0, 1, ..., |V|-1] into a set of required vertices R = [0, 1, ..., s-1] and a set of Steiner vertices S = [s, s+1, ..., |V|-1], the General Steiner Tree problem is a problem of finding a subset S' ⊆ S of the Steiner vertices and a spanning tree T = (R ⋃ S', E) of minimum weight. The weight of the tree T is simply the sum of its edge weights.
This General Steiner Tree problem is a generalization of the more well-known Minimum Spanning Tree problem (MST).
Unlike MST, which has a polynomial solution (e.g., O(E log V) Kruskal's/Prim's algorithm), this general Steiner-Tree problem is an NP-hard combinatorial optimization problem.
Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.
There are a few other variants of this general Steiner-Tree problem, e.g., the Euclidean-Steiner-Tree and the Metric-Steiner-Tree problems.
In the Euclidean-Steiner-Tree problem, there are V distinct points (set R) on an Euclidean (2-dimensional) plane, the job is to find a(n additional, possibly empty) set of Steiner points S (can be anywhere in the 2-D plane) and a spanning tree T = (R ⋃ S, E) such that the weight of T is minimized. The weight of any two points is simply the Euclidean distance of those two points.
In the Metric-Steiner-Tree problem, it is like the Euclidean-Steiner-Tree, but this time the additional Steiner points are given as a set of S upfront. The weight of any two points must satisfy metric space properties.
Euclidean-Steiner Tree, Metric-Steiner-Tree, and the general Steiner-Tree that is visualized in this website, are all NP-hard optimization problems.
Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.
View the visualisation of the selected Steiner-Tree algorithms here.
Originally, all vertices and edges in the input graph are colored with the standard black outline. As the visualization goes on, the color light blue will be used to denote the set of required vertices R and the color orange will be used to show Steiner vertices that are currently used.
At the end of the selected Steiner-Tree algorithm, we show the best spanning tree = the Steiner tree T.
Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.
Terdapat dua metode berbeda untuk membuat graf masukan:
- Ubah graf: Anda dapat mengubah graf tak berbobot tak terarah.
- Graf contoh: Anda dapat memilih dari graf contoh terhubung tak berbobot tak berarah yang tersedia.
Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, ←/→ to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.
There are 3 special cases of the general Steiner-Tree problem with polynomial solutions:
- s = 2, that implies that the only required vertices R = [0, 1], we can simply run O((V+E) log V) Dijkstra's algorithm to find the Shortest Path Spanning Tree that connects source vertex 0 with destination vertex 1 (or vice versa). This spanning tree will also be the required Steiner Tree.
- s = |V|, that implies that all of the |V| vertices, i.e., R = [0, 1, ..., |V|-1] are all required, we can simply run O(E log V) Kruskal's or Prim's algorithm to find the full Minimum Spanning Tree (MST) of the entire graph. This MST will also be the required Steiner Tree.
- If G is a tree: Details TBA.
But when s = [3, 4, ..., |V|-2], we have no choice but to run exponential algorithms as these cases fall into general cases of the NP-hard general Steiner-Tree problem.
One possible way is to try all possible subsets of the |V|-s vertices that can be part of the optimal Steiner Tree. Each time, we combine vertices in R = [0, 1, ..., s-1] with the currently chosen subset of potential Steiner vertices, run an O(E) Kruskal's algorithm (without re-sorting the edge list by weight anymore) for each of the 2|V|-s possible subsets, and report the best Steiner Tree. This is an exponential algorithm and this visualization page shows this algorithm.
There is a more optimized exponential algorithm called the Dreyfus-Wagner Dynamic Programming (DP) algorithm that avoids recomputation of sub-problems.
Unfortunately this part has not been digitized/visualized yet and is in the pipeline.
Please see CS4234 lecture note for the details.
You have reached the last slide. Return to 'Exploration Mode' to start exploring!
Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.
Ubah Graf
Graf-Graf Contoh
Exact
Approximation