Pode-se usar o algoritmo de Prim ou o algoritmo de Kruskal para encontrar o spanning tree / graph mínimo de uma coleção de vértices / nós e arestas / links. O que eu quero, no entanto, é um algoritmo que encontre o gráfico de alcance mínimo dessa coleção, mas o gráfico resultante precisa incluir apenas nós arbitrariamente escolhidos, em vez de todos os nós. Tudo bem se o gráfico resultante incluir mais nós do que apenas os necessários.

Algum algoritmo existe? Talvez se pudesse usar o algoritmo de Prim (ou de Kruskal) depois de modificar o gráfico para incluir apenas os nós necessários? Mas não tenho certeza de como modificar o gráfico para fazer isso enquanto mantém sua conexão.

Por exemplo, digamos que temos um gráfico inicial em forma de diamante (com custos de links entre parênteses):

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

Agora, arbitrariamente decidimos que apenas os nós A e D são necessários. Se começamos em A, ainda queremos que ele tome o caminho da esquerda, porque ((2 + 2) <(1 + 5)).

Digamos que modifiquemos o gráfico ligeiramente:

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

Se decidirmos que apenas os nós A, D e E são necessários, percebemos que o caminho com o custo mínimo não é necessariamente aquele com o menor número de links. Tomar A - B - D e A - C - E custa 7, mas A - C - D e C - E custa 8.