Steiner Tree in Graph — Explained
Problem Definition
Given an undirected graph with non-negative edge weights and a subset of vertices (terminals), the Steiner Tree in graph is an MST “T” of minimum weight that contains all given terminals (but may include additional vertices).
Input
Given Terminals — > “1,3,5,6” i.e Steiner Tree should contain “1,3,5,6”
Logic
Step 1
Terminal “1” is added to T.
Step 2 (Repeat until all Terminals are added to “T”)
a) “Select a terminal x, not in T that is closest to a vertex in T”.
The terminals to be considered are “3”, “5” and “6”.
T has only one Vertex which is “1”.
Applying Dijkstra’s Algorithm,
3→1 = 8 (3–2, 2–1 being the path).
5 →1 = 10 (5–4, 4–3, 3–2, 2–1 being the path).
6 →1 = 6 (6–1 being the path).
The terminal x not in T that is closest to a vertex in T is “6” (with cost of 6)
i.e x = 6
b) “Adding to T the shortest path that connects x with T”.
“1” with “6” is minimum.
So Terminal “6” is added to T.
The edge “6 —1 = 6” is included.
Back to Step 2
The terminals to be considered are “3” and “5”.
T has “1” and “6”.
a) “Select a terminal x, not in T that is closest to a vertex in T”.
The terminal x not in T that is closest to a vertex in T is either “3” or “5” (with cost of “5”).There is a tie and we choose x = 3.
T has “1” and “6”.
We can either connect “3” with “1” or “3” with “6”.
Applying Dijkstra’s Algorithm,
“3” with “1”:
3→1 = 8 (3–2, 2–1 being the path).
“3” with “6”:
3 →6 = 5 (3–4, 4–6 being the path).
b) “Adding to T the shortest path that connects x with T”.
“3” with “6” is minimum.
So Terminal “3” is added to T.
The edge “3 — 4 = 1” is included.
The edge “4 — 6 = 4” is included.
Since the edge “3 — 4 = 1” is included, the vertex “4” is also added to T.
Back to Step 2
The terminal to be considered is “5”.
T has “1”, “3”, “4” and “6”.
a) “Select a terminal x, not in T that is closest to a vertex in T”.
The terminal x not in T that is closest to a vertex in T is “5” (with cost “2”).
i.e x = 5.
We can connect “5” with “1” or “5” with “3” or “5” with “4” or “5” with “6”.
Applying Dijkstra’s Algorithm,
“5” with “1”:
5→1 = 10 (5–4, 4–3, 3–2, 2–1 being the path).
“5” with “3”:
5 →3 = 2(5–4, 4–3 being the path).
“5” with “4”:
5→4 = 1(5–4 being the path).
“5” with “6”:
5 →6 = 5 (5–4, 5–6 being the path).
b) “Adding to T the shortest path that connects x with T”.
“5” with “4” is minimum.
So Terminal “5” is added to T.
The edge “5–4 = 1” is included.
Now, we have added all terminals to T. Step 2 is completed.
Steiner Tree is formed successfully.
Output
The vertices in T are “1”, “3”, “4”, “5” and “6”.
The edges in T are
“ 1–6= 6”
“4–3= 1”
“4–5= 1”
“4–6 = 4”
The Cost of Steiner Tree is “12” (6+1+1+4).
Code
The implementation of the above logic is available at https://github.com/rkarthik3cse/Steiner-Tree
References
