Steiner tree problem

Steiner tree problem can be see to the mix between a Minimum Spanning Tree problem and a shortest path problem. It tries to find the shortest network between the vertices of a graph.

The problem can be illustrated by building the less roads possible to connect cities together.

Sometimes, we can add the option to add vertices (i.e. Steiner nodes) to the graph to decrease the total length of the graph.

It is considered as a NP-hard problem.