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

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

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

    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.