Tenho um gráfico de peso positivo não direcionado (V, E) para o qual desejo uma árvore de abrangência mínima cobrindo um subconjuntok dos vérticesV (o problema da árvore Steiner

Não estou limitando o tamanho da árvore de abrangência parak vértices; sim, eu sei exatamentequa kértices devem ser incluídos no MS

Iniciando a partir de todo o MST, eu poderia analisar as bordas / nós até obter o menor MST que contém todos osk.

Eu posso usar o algoritmo de Prim para obter o MST inteiro e começar a excluir bordas / nós enquanto o MST do subconjunto k não for destruído; alternativamente, posso usar o Floyd-Warshall para obter os caminhos mais curtos de todos os pares e de alguma forma unir os caminhos. Existem maneiras melhores de abordar isso?