У меня есть неориентированный граф с положительным весом ребер (V, E) , для которого мне нужно минимальное остовное дерево, покрывающее подмножество k вершин V (проблема дерева Штейнера).
Я не ограничиваю размер остовного дерева до k вершин; скорее я точно знаю , какие k вершин должны быть включены в MST.
Начиная со всего MST, я мог сокращать ребра / узлы, пока не получил наименьшее MST, содержащее все k .
Я могу использовать алгоритм Прима для получения всего MST и начать удаление ребер / узлов, пока MST подмножества k не уничтожается; в качестве альтернативы я могу использовать метод Флойда-Уоршалла, чтобы получить кратчайшие пути для всех пар и как-то объединить пути. Есть ли лучшие способы подойти к этому?