steiner_tree(G, terminal_nodes, weight='weight')¶
Return an approximation to the minimum Steiner tree of a graph.
The minimum Steiner tree of
Gw.r.t a set of
terminal_nodesis a tree within
Gthat spans those nodes and has minimum size (sum of edge weights) among all such trees.
The minimum Steiner tree can be approximated by computing the minimum spanning tree of the subgraph of the metric closure of G induced by the terminal nodes, where the metric closure of G is the complete graph in which each edge is weighted by the shortest path distance between the nodes in G . This algorithm produces a tree whose weight is within a (2 - (2 / t)) factor of the weight of the optimal Steiner tree where t is number of terminal nodes.
G (NetworkX graph)
terminal_nodes (list) – A list of terminal nodes for which minimum steiner tree is to be found.
Approximation to the minimum steiner tree of
- Return type
For multigraphs, the edge between two nodes with minimum weight is the edge put into the Steiner tree.
Steiner_tree_problem on Wikipedia. https://en.wikipedia.org/wiki/Steiner_tree_problem