# Steiner Tree Problem

What's difficult is in the middle.

Shortest Path Problem:

Input: a graph and two nodes

Output: a minimum-cost path between the two nodes

Steiner Tree Problem:

Input: a graph and some nodes

Output: a minimum-cost tree which covers all the input nodes

Minimum Spanning Tree Problem:

Input: a graph

Output: a minimum spanning tree

We can see Steiner tree problem sits in between the shortest path problem and the minimum spanning tree problem. Steiner tree problem does not have a polynomial algorithm unlike the other two problems. What's difficult is in the middle.