Algoritmo de Dijkstra
- Propuesto por
- Edsger W. Dijkstra
- Año
- 1956
- Tipo
- algorithm
- Familia
- Graph Algorithms
Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés
¿Qué hace?
El Algoritmo de Dijkstra, introducido por Edsger W. Dijkstra en 1956, es uno de los algoritmos más fundamentales en la informática para resolver el problema del camino más corto de una única fuente.
Encuentra el camino más corto desde un vértice de inicio a todos los demás vértices en un grafo ponderado con pesos de arista no negativos.
La intuición detrás del método
El algoritmo mantiene un conjunto de vértices cuyas distancias más cortas desde la fuente ya se conocen, y expande iterativamente este conjunto seleccionando el vértice no procesado más cercano y actualizando las distancias a sus vecinos. La clave es la propiedad codiciosa (greedy): una vez que se selecciona un vértice, su distancia desde la fuente es definitiva porque todos los pesos de las aristas son no negativos, por lo que cualquier camino más largo a través de vértices no visitados no puede ser más corto. Esto garantiza la corrección y la optimalidad.
Historia
Edsger W. Dijkstra publicó su algoritmo en 1959 en un artículo de tres páginas que se convertiría en una de las obras más citadas en informática. El algoritmo surgió del trabajo de Dijkstra en la computadora ARMAC en Ámsterdam. A lo largo de décadas, se han realizado numerosas mejoras, incluidas mejores estructuras de datos (montículos de Fibonacci que logran una complejidad O(E+VlogV)) y variantes bidireccionales. El algoritmo sigue siendo central para los protocolos de enrutamiento modernos como OSPF en redes.
Cuándo usarlo
Aplicar el algoritmo de Dijkstra al encontrar caminos más cortos en grafos con pesos de arista no negativos. Es ideal para sistemas de navegación, enrutamiento de redes y cualquier problema de grafos que requiera caminos óptimos. Úselo para caminos más cortos de una única fuente a todos los vértices. Para grafos con pesos negativos, use Bellman-Ford en su lugar. Para búsqueda bidireccional o guía heurística, considere el algoritmo A*.
Limitaciones y consideraciones
- No puede manejar grafos con pesos de arista negativos
- Calcula caminos más cortos a todos los vértices, no solo a un destino (aunque puede terminar antes)
- Menos eficiente que A* cuando hay información heurística disponible
- Requiere que se descubran todos los vértices; ineficiente para conectividad muy dispersa
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- Fácil de entender e implementar con claras garantías de corrección
- Eficiente con estructuras de datos adecuadas: O((V+E)logV) con montículo binario, O(V²) con array
- Óptimo para grafos con pesos no negativos; demuestra la optimalidad de los caminos calculados
- Funciona tanto en grafos dirigidos como no dirigidos
- Base para numerosas extensiones y algoritmos relacionados
Aplicaciones
- Sistemas GPS y de navegación: encontrar rutas más cortas para vehículos y peatones
- Protocolos de enrutamiento de red: determinar rutas óptimas para paquetes de datos en redes informáticas
- Redes sociales: encontrar caminos de conexión más cortos entre usuarios o influencers
- Desarrollo de juegos: búsqueda de caminos para inteligencia artificial y movimiento de personajes no jugadores
- Planificación de movimiento de robots: cálculo de trayectorias óptimas para sistemas robóticos
- Telecomunicaciones: optimización de rutas de llamadas y caminos de propagación de señales
Cómo funciona
Cómo funciona
Establecer la distancia a la fuente como cero y todas las demás distancias como infinito. Marcar todos los vértices como no visitados y crear una cola de prioridad.
Seleccionar el vértice no visitado con distancia mínima desde la fuente utilizando la cola de prioridad.
Para cada vecino del vértice seleccionado, si el camino a través del vértice seleccionado ofrece una distancia más corta, actualizar la distancia del vecino y añadirlo a la cola de prioridad.
Errores comunes
- Usar el algoritmo en grafos con pesos negativos, lo que resulta en caminos más cortos incorrectos
- Implementación ineficiente con operación de extracción-mínimo en tiempo lineal, lo que lleva a un rendimiento deficiente
- No actualizar correctamente las distancias cuando los vecinos son revisitados a través de diferentes caminos
Preguntas frecuentes
¿Por qué falla el algoritmo de Dijkstra en pesos negativos?
El algoritmo asume que una vez que un vértice se finaliza, no se puede encontrar un camino más corto a través de vértices no visitados. Con pesos negativos, un camino más largo podría mejorar más tarde cuando se usa una arista negativa, violando esta suposición.
¿Qué estructura de datos se debe usar para la cola de prioridad?
Los montículos binarios proporcionan operaciones O(logV) tanto para la inserción como para la extracción, lo que resulta en una complejidad total de O((V+E)logV). Los montículos de Fibonacci logran O(E+VlogV) pero tienen grandes factores constantes. Los arrays funcionan bien para grafos pequeños.
¿Cómo puede el algoritmo de Dijkstra encontrar el camino a un destino específico?
Terminar el algoritmo tan pronto como se selecciona el vértice de destino (su distancia se finaliza), evitando cálculos innecesarios. Alternativamente, reconstruir el camino manteniendo punteros padre durante la ejecución.
¿Se puede usar el algoritmo de Dijkstra en grafos no dirigidos?
Sí, los grafos no dirigidos se pueden representar como grafos dirigidos con aristas en ambas direcciones para cada arista no dirigida, cada una con el mismo peso. El algoritmo funciona de manera idéntica en la representación bidireccional.
Métodos relacionados
Fuentes
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
Abrir referencia DOICopiado.Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
ISBN: 978-0-262-03384-8Copiado.