Se puede usar el algoritmo de Prim o el algoritmo de Kruskal para encontrar el árbol / gráfico de expansión mínima de una colección de vértices / nodos y bordes / enlaces. Sin embargo, lo que quiero es un algoritmo que encuentre el gráfico de expansión mínimo de esta colección, pero el gráfico resultante debe incluir solo los nodos elegidos arbitrariamente, en lugar de todos los nodos. Está bien si el gráfico resultante incluye más nodos que solo los necesarios.

¿Existe tal algoritmo? ¿Tal vez uno podría usar el algoritmo de Prim (o Kruskal) después de modificar el gráfico para incluir solo los nodos necesarios? Pero, no estoy seguro de cómo modificar el gráfico para hacerlo mientras se mantiene su conexión.

Por ejemplo, digamos que tenemos un gráfico de inicio en forma de diamante (con los costos de los enlaces entre paréntesis):

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

Ahora, decidimos arbitrariamente que solo los nodos A y D son necesarios. Si comenzamos en A, todavía queremos que tome el camino de la izquierda, porque ((2 + 2) <(1 + 5)).

Digamos que modificamos ligeramente la gráfica:

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

Si decidimos que solo se necesitan los nodos A, D y E, nos damos cuenta de que la ruta con el costo mínimo no es necesariamente la que tiene menos enlaces. Tomar A - B - D y A - C - E cuesta 7, pero A - C - D y C - E cuesta 8.