Scribd
Cargar
7 vistas1 página

Algoritmos de Dijkstra y Ciclos de Hamilton

El documento compara el algoritmo de Dijkstra, que encuentra la ruta más corta en grafos con pesos no negativos, con el problema de ciclos de Hamilton, que busca un ciclo que recorra cada vértice una vez. Dijkstra es determinista, eficiente y se utiliza en diversas aplicaciones como navegación y logística, mientras que el ciclo de Hamilton es NP-completo y computacionalmente costoso. Ambos tienen ventajas y desventajas en sus respectivos usos, destacando la optimización de rutas en el caso de Dijkstra y la complejidad en el caso de Hamilton.

Cargado por

Derek Rex
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
7 vistas1 página

Algoritmos de Dijkstra y Ciclos de Hamilton

El documento compara el algoritmo de Dijkstra, que encuentra la ruta más corta en grafos con pesos no negativos, con el problema de ciclos de Hamilton, que busca un ciclo que recorra cada vértice una vez. Dijkstra es determinista, eficiente y se utiliza en diversas aplicaciones como navegación y logística, mientras que el ciclo de Hamilton es NP-completo y computacionalmente costoso. Ambos tienen ventajas y desventajas en sus respectivos usos, destacando la optimización de rutas en el caso de Dijkstra y la complejidad en el caso de Hamilton.

Cargado por

Derek Rex
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

** Derek Joann Alvirde Mejía ** ** Estructura de Datos ** ** Karina Torres Reyes ** ** 03 de diciembre de 2025 **

CRITERIO ALGORITMO DE DIJKSTRA CICLOS DE HAMILTON


DEFINICION Algoritmo que encuentra la ruta mas corta desde un nodo originan hacia todos los Problema que busca un ciclo que recorra cada vértice exactamente una vez y regrese
demás nodos en un grafo con pesos no negativos. al punto inicial.

CARACTERISTICAS - Determinista y eficiente. - Es un problema NP-completo.


- Usa una estructura de datos; cola de prioridad. - No existe un algoritmo eficiente general.
- Opera solo con pesos no negativos. - Requiere explorar muchas combinaciones.
- Encuentra rutas óptimas. - Enfocado en recorrer todos los nodos.

USOS - Cálculo de rutas más cortas en redes. - Optimización de rutas completas.


- Sistemas de navegación. - Problema del viajante (TSP).
- Redes de transporte y logística. - Diseño de circuitos.
- Análisis de grafos en IA y videojuegos. - Secuenciación de tareas o máquinas.
- Redes de comunicación. - Exploración exhaustiva de redes.

VENTAJAS - Muy rápido y eficiente. - Permite obtener rutas globales óptimas en problemas complejos.
- Fácil de implementar. - Ayuda a modelar problemas reales de planificación completa.
- Garantiza solución óptima.
- Funciona bien en grafos grandes.

DESVENTAJAS - No funciona con pesos negativos. - Computacionalmente costoso.


- Encuentra rutas punto a punto, no recorridos globales de todos los nodos. - Difícil de resolver para grafos grandes.
- No optimiza ciclos completos. - No existe algoritmo universal eficiente.

DONDE SE USA - Transporte y logística - Logística


- Telecomunicaciones - Manufactura
- Videjuegos - Electrónica
- Robótica - Planificación de tareas (scheduling)
- Energía

Referencias (APA 7)

Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269–271. [Link]

Gondran, M., & Minoux, M. (1984). Graphs and algorithms. John Wiley & Sons.

Gross, J. L., & Yellen, J. (2018). Graph theory and its applications (3rd ed.). Chapman & Hall/CRC.

Korte, B., Vygen, J., & Jünger, M. (2018). Combinatorial optimization: Theory and algorithms (6th ed.). Springer.

Papadimitriou, C. H. (1994). Computational complexity. Addison-Wesley.

Wilson, R. J. (2010). Introduction to graph theory (5th ed.). Pearson.

También podría gustarte