El algoritmo de Dijkstra le encontrará el camino más corto, no se garantiza que produzca un camino hamiltoniano. No estoy seguro de lo que quieres decir con tomar el más corto de esos . Un consejo que tuve que aprender hace un tiempo es, por lo general, si te vuelves impreciso al describir un algoritmo, es ahí donde surgen los problemas.
¿Voy a suponer que quieres decir que unirás los caminos más cortos entre todos los pares? ¿Cuál de los caminos más cortos? Algunos de estos caminos probablemente se superpongan. El camino más corto entre dos vértices no es necesariamente un camino hamiltoniano, por lo que podría terminar uniendo los caminos más cortos incorrectos . Por lo que ha sugerido, no parece funcionar o, en el mejor de los casos, parece incompleto.
Parece que puede tener algunas ideas que se asemejan al algoritmo de programación dinámica para el Problema del vendedor ambulante, consulte el Algoritmo Held-Karp (discutido por primera vez aquí: https: //ucilnica1213.fmf.uni-lj…. Y http: // www .akira.ruc.dk / ~ keld / te …). Este algoritmo de programación dinámica seleccionará la ruta más corta correcta a medida que agrega cada vértice. De cualquier manera, le animo a que consulte el artículo de Wikipedia sobre este problema, creo que lo explica lo suficientemente bien como para continuar: problema de la ruta de Hamilton – Wikipedia. Este algoritmo de programación dinámica toma tiempo exponencial.
- ¿Existe un libro que enseñe algoritmos, estructuras de datos y otros conceptos básicos de informática de una manera divertida?
- ¿Cómo funciona la transformación cuántica de Fourier?
- ¿Cuál es la mejor manera de aprender a escribir algoritmos?
- Cómo resolver este problema de matrices en programación en C
- Cómo resolver este problema de integración definitiva
¡Espero que esto ayude!
