I have an undirected, positive-edge-weight graph (V,E) for which I want a minimum spanning tree covering a subset k of vertices V (the Steiner tree problem).

I'm not limiting the size of the spanning tree to k vertices; rather I know exactly which k vertices must be included in the MST.

Starting from the entire MST I could pare down edges/nodes until I get the smallest MST that contains all k.

I can use Prim's algorithm to get the entire MST, and start deleting edges/nodes while the MST of subset k is not destroyed; alternatively I can use Floyd-Warshall to get all-pairs shortest paths and somehow union the paths. Are there better ways to approach this?

algorithm tree graph-theory graph-algorithm
Edit
Report