Trusted answers to developer questions

Arooj Fatima

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Named after Jakob Steiner, the **Steiner Tree Problem** covers a class of problems in
combinatorial optimization.

Steiner Tree Problems require an optimal interconnect for a given set of objects and a predefined objective function. The Steiner Tree Problem in graphs is one of the variants of this problem.

A **Steiner Tree** is an undirected, weighted graph with a minimum-weight tree that connects a selected set of vertices, called **terminals**.

**Steiner vertices:**

The tree may include non-terminals, which are called Steiner points or Steiner vertices.

Some of the areas where a Steiner Tree is used:

VLSI design Very-large-scale integration - network routing
- wireless communications
- computational biology

Given:

- an
graphundirected edges that do not have a direction - non-negative edge weights
- a subset of vertices/ terminals

The Steiner Tree in a graph is a

Start with a

Select a terminal (x) closest to a vertex in the subtree, but not within the subtree itself.

Add the shortest path that connects x to the subtree.

There are approximate algorithms to solve the same problem. The Steiner Tree problem is

; there are no polynomial-time solutions that always give optimal cost. NP-Hard nondeterministic polynomial time

Follow the steps below to find the solution in subtree T.

Step 1: Add terminal b to subtree T.

Step 2: Select a terminal that is closest to a vertex in T, but not in T itself.

Now the vertices connected to b are:

- a (4)
- c (6)
- d (5)

Choose the terminal with the minimum weight i.e. vertex a.

Step 3: Repeat step 2 by following *Dijkstra’s Algorithm* until all vertices are traversed.

Step 4: The final subtree will be as follows.

*Formula for Dijkstra’s Algorithm*

dx(y) → cost of least-cost path from x to y

then,

dx(y) = *v*

To find the

The cost of `Steiner Tree`

is:

path: b-a-d-c-e-f-g

cost: 0+4+5+6+7+7+10

Cost = 39

RELATED TAGS

community creator

steiner

tree

graph

CONTRIBUTOR

Arooj Fatima

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring

Related Courses