Алгоритм нахождения минимального остовного дерева выбранных вершин

Можно использовать Prim 'Алгоритм или КрускальАлгоритм поиска минимального остовного дерева / графа набора вершин / узлов и ребер / связей. Однако мне нужен алгоритм, который находит минимальный остовный граф этой коллекции, но полученный граф должен включать только произвольно выбранные узлы, а не все узлы. Это'Хорошо, если полученный граф включает больше узлов, чем просто необходимых.

Существует ли такой алгоритм? Возможно, можно просто использовать Prim 'с (или Крускальs) алгоритм после изменения графа для включения только необходимых узлов? Но я'Я не уверен, как изменить график, чтобы сделать это при сохранении его связности.

Например, скажем, у нас есть начальный граф в форме ромба (со стоимостью ссылок в скобках):

    A
(2)/ \(1)
  B   C
(2)\ /(5)
    D

Теперь мы произвольно решаем, что нужны только узлы A и D. Если мы начали в А, мыЯ все еще хочу, чтобы он пошел по левому пути, потому что ((2 + 2) < (1 + 5)).

Скажем, мы немного изменим график:

    A
(2)/ \(1) (2)
  B   C ------E
(2)\ /(5)
    D

Если мы решим, что нужны только узлы A, D и E, мы поймем, что путь с минимальной стоимостью не обязательно является тем, который имеет наименьшее количество ссылок. Взятие A - B - D и A - C - E стоит 7, но A - C - D и C - E стоит 8.

Ответы на вопрос(1)

Ваш ответ на вопрос