Camino más corto entre tres nodos de un grafo

Question

Conozco el algoritmo de Dijkstra para encontrar el camino más corto entre 2 nodos, pero ¿hay alguna forma de encontrar el camino más corto entre 3 nodos entre $n$ ¿nodos? He aquí los detalles:

Tengo $n$ nodos, algunos de los cuales están conectados directamente y otros indirectamente, y necesito encontrar el camino más corto entre 3 de ellos.

Por ejemplo $n = 6$ nodos etiquetados de A a F, y el siguiente gráfico:

A-->B-->C
A-->D-->E
D-->F

¿Cómo puedo encontrar el camino más corto entre los tres nodos (A,E,F)?

Busco una solución similar al algoritmo del camino más corto de Dijkstra, pero para 3 nodos en lugar de 2.
Tenga en cuenta :
1- El Nodo de partida es A
2- El secuencial no es importante sólo el camino tiene que cubrir todos estos nodos
3- No hay retorno a A
Vea el diagrama Imagen Saludos y gracias
Nahed

Answer 1

Para el caso de un nodo de inicio S y dos nodos de destino X e Y, se podría utilizar el siguiente algoritmo:

Utiliza el algoritmo del camino más corto de Dijkstra para encontrar el camino más corto de S a X y el camino más corto de S a Y. Si el camino de S a X es más corto, utiliza el algoritmo del camino más corto de Dijkstra para encontrar el camino más corto de X a Y, y sigue los caminos encontrados de S a X y luego de X a Y. De lo contrario (si el segundo camino es más corto), encuentra el camino más corto de Y a X y sigue los caminos encontrados de S a Y y luego de Y a X.

Como siempre utiliza el algoritmo de Dijkstra exactamente 3 veces, es asintóticamente igual de eficiente que el algoritmo de Dijkstra.

---

Ten en cuenta que, como señalan Tyler Olsen y ml0105, si de hecho hay un número variable de nodos por los que tienes que pasar en lugar de sólo 3, este problema es NP-Difícil.

Answer 2

Yo diría que la solución de Phicar del algoritmo de todos los pares y caminos más cortos de Floyd-Warshall es tu mejor opción. Por supuesto, este problema es NP-Hard. Es el problema del camino hamiltoniano óptimo, que es equivalente al problema del viajante de comercio.

El algoritmo Floyd-Warshall puede ejecutarse en tiempo polinómico. Sin embargo, mientras que la secuencia de los vértices puede no importarte, sí importa para minimizar el coste total. Así que su reducción es realmente de SAT. Realmente tienes que probar combinaciones hasta que obtengas el camino de tamaño mínimo.