Сначала разделите граф на связанные компоненты. После этого рассматривайте только компонент, содержащий узел root. Выберите верхние k вершин в порядке неубывания по весу. Обратите внимание, что ни существование, ни уникальность решения не гарантируются.
Предостережение
В описании проблемы может отсутствовать что-то, так как цикличность граф не фигурирует в решении.
Возможно, нужно минимизировать сумму весов всех вершин дерева, составленного из путей от узлов решения до root? Заголовок вопроса предполагает это, но тело говорит об обратном.
В случае, если это предположение верно, необходимо решить задачу взвешенного по узлам дерева Штейнера , ограниченную экземплярами с k. размер клемм.