steiner_tree(graph, terminal_nodes, weight_fn, /)#

Return an approximation to the minimum Steiner tree of a graph.

The minimum tree of graph with regard to a set of terminal_nodes is a tree within graph that spans those nodes and has a minimum size (measured as the sum of edge weights) amoung all such trees.

The minimum steiner tree can be approximated by computing the minimum spanning tree of the subgraph of the metric closure of graph induced by the terminal nodes, where the metric closure of graph is the complete graph in which each edge is weighted by the shortest path distance between nodes in graph.

This algorithm [1] produces a tree whose weight is within a \((2 - (2 / t))\) factor of the weight of the optimal Steiner tree where \(t\) is the number of terminal nodes. The algorithm implemented here is due to [2] . It avoids computing all pairs shortest paths but rather reduces the problem to a single source shortest path and a minimum spanning tree problem.

  • graph (PyGraph) – The graph to compute the minimum Steiner tree for

  • terminal_nodes (list) – The list of node indices for which the Steiner tree is to be computed for.

  • weight_fn – A callable object that will be passed an edge’s weight/data payload and expected to return a float. For example, you can use weight_fn=float to cast every weight as a float.


An approximation to the minimal steiner tree of graph induced by terminal_nodes.

Return type:



ValueError – when an edge weight with NaN or negative value is provided.