Algoritmos de Ruta Más Corta
Los algoritmos de ruta más corta calculan las rutas de peso mínimo entre vértices en un grafo ponderado, con diferentes algoritmos adecuados para pesos no negativos, pesos negativos y consultas de todos los pares versus fuente única.
Definition
Una ruta más corta entre dos vértices en un grafo ponderado es una ruta cuyo peso total de arista es mínimo; los algoritmos de ruta más corta calculan dichas rutas y sus distancias, ya sea desde una fuente a todos los vértices o entre todos los pares de vértices.
Scope
Este tema cubre las rutas más cortas de fuente única (algoritmo de Dijkstra para pesos no negativos, Bellman-Ford para grafos con pesos negativos y para detectar ciclos negativos), las rutas más cortas de todos los pares (Floyd-Warshall, algoritmo de Johnson) y las rutas más cortas en grafos dirigidos acíclicos. Trata el principio de relajación común a estos métodos y el papel de las colas de prioridad en la implementación eficiente. Excluye las rutas más cortas no ponderadas obtenidas por búsqueda en anchura, cubiertas en el tema de recorrido de grafos.
Core questions
- ¿Cómo la relajación de aristas ajusta progresivamente las estimaciones de distancia hacia las verdaderas distancias más cortas?
- ¿Por qué el algoritmo de Dijkstra requiere pesos de arista no negativos para ser correcto?
- ¿Cómo maneja Bellman-Ford los pesos negativos y detecta ciclos negativos?
- ¿Cuándo es más eficiente calcular las rutas más cortas de todos los pares que repetir un método de fuente única?
- ¿Cómo afectan las elecciones de la cola de prioridad al tiempo de ejecución del algoritmo de Dijkstra?
Key concepts
- relajación de aristas
- rutas más cortas de fuente única
- algoritmo de Dijkstra
- algoritmo de Bellman-Ford
- ciclos de peso negativo
- rutas más cortas de todos los pares
- algoritmo de Floyd-Warshall
- implementación de cola de prioridad
Key theories
- Relajación de aristas y selección codiciosa
- Los algoritmos de ruta más corta relajan repetidamente las aristas, reemplazando una estimación de distancia cuando se encuentra una ruta más corta; el algoritmo de Dijkstra finaliza de forma codiciosa el vértice no resuelto más cercano, lo cual es correcto precisamente porque los pesos de las aristas son no negativos.
- Programación dinámica para rutas de todos los pares
- El algoritmo de Floyd-Warshall calcula las rutas más cortas de todos los pares mediante un programa dinámico sobre vértices intermedios, con un tiempo de ejecución cúbico y manejando naturalmente los pesos de arista negativos (sin ciclos negativos).
Clinical relevance
Los algoritmos de ruta más corta impulsan los servicios de navegación y mapeo, los protocolos de enrutamiento de paquetes en redes, la planificación de rutas en logística y cualquier sistema que encuentre rutas de menor costo a través de una red ponderada, incluyendo la búsqueda de caminos en juegos y los cálculos de distancia de recursos en el análisis espacial.
History
Dijkstra publicó su algoritmo de ruta más corta de fuente única en 1959. El algoritmo de Bellman-Ford, que maneja pesos negativos, surgió del trabajo de Bellman, Ford y Moore a finales de la década de 1950. El algoritmo de Floyd de 1962, basado en el método de cierre transitivo de Warshall, proporcionó una solución compacta para todos los pares que sigue siendo un estándar.
Key figures
- Edsger W. Dijkstra
- Richard Bellman
- Lester Ford
- Robert W. Floyd
Related topics
Seminal works
- dijkstra1959
- floyd1962
- cormen2009
Frequently asked questions
- ¿Por qué el algoritmo de Dijkstra no puede manejar pesos de arista negativos?
- El algoritmo de Dijkstra finaliza el vértice no resuelto más cercano y nunca lo vuelve a visitar, asumiendo que ninguna ruta posterior puede ser más corta. Una arista negativa podría crear una ruta más corta después de que un vértice se haya establecido, rompiendo la suposición. En su lugar, se utiliza Bellman-Ford, que relaja todas las aristas repetidamente.
- ¿Cuándo debo usar un algoritmo de todos los pares en lugar de ejecutar Dijkstra desde cada vértice?
- Para grafos densos o cuando se necesitan muchas o todas las distancias origen-destino, la sencilla computación cúbica en tiempo de Floyd-Warshall para todos los pares suele ser preferible. Para grafos dispersos, ejecutar Dijkstra (o el algoritmo de Johnson para pesos negativos) desde cada fuente puede ser asintóticamente más rápido.