Algoritmo de Dijkstra
Tu planificador de rutas conoce el camino más rápido desde tu puerta hasta casi cualquier lugar. En el corazón de esa idea hay un algoritmo que Edsger Dijkstra ideó en unos veinte minutos en 1956: crecer hacia fuera desde el origen y terminar siempre primero el lugar más cercano.
La idea
Imagina pueblos unidos por carreteras de distintas longitudes. La pregunta es: ¿cuál es el camino más corto desde mi pueblo hasta cada uno de los demás? La búsqueda en anchura la responde cuando todas las carreteras cuentan igual, pero aquí una ruta con más carreteras puede ser más corta. El algoritmo de Dijkstra guarda, para cada pueblo, la distancia más corta encontrada hasta ahora, y hace crecer una región de pueblos cuya distancia es segura, añadiendo siempre el pueblo más cercano que aún no es seguro.
Paso a paso
Da al origen la distancia 0 y a todos los demás nodos infinito. Pon el origen en una cola de prioridad, una cola que siempre entrega el nodo con la menor distancia. Toma ese nodo; su distancia ya es definitiva. Para cada vecino que no sea definitivo, calcula la distancia pasando por este nodo: su distancia más la longitud de la arista. Si es menor que la distancia que tenía el vecino, redúcela, recuerda este nodo como el camino hasta él y pon el vecino en la cola. Esto se llama relajar una arista. Repite hasta que la cola esté vacía, o hasta que el destino salga de ella.
Un ejemplo
Toma las aristas A–B de longitud 4, A–C 1, B–C 2, B–D 1, C–D 5 y D–E 3, y empieza en A. Al tomar A, B recibe distancia 4 y C distancia 1. C es el más cercano, así que es definitivo con 1; pasando por C, B baja a 1 + 2 = 3 y D recibe 1 + 5 = 6. Ahora B es el más cercano, definitivo con 3, y pasando por B, D baja a 3 + 1 = 4. D es definitivo con 4 y da a E 4 + 3 = 7. Así que el camino más corto de A a E es A → C → B → D → E, de longitud 7, aunque A → B → D → E usa menos aristas y tiene longitud 8.
Por qué es correcto
Supón que el nodo X es el más cercano de la cola, a distancia d. Cualquier otro camino desde el origen hasta X debe salir en algún momento de la región de nodos definitivos, y el primer nodo que alcanza fuera de esa región está en la cola, así que ya está al menos a d. El resto del camino no puede acortarlo, porque ninguna arista es negativa. Por tanto, d es la distancia más corta hasta X. Con una arista negativa ese argumento falla; en su lugar se usa el algoritmo de Bellman–Ford, que relaja todas las aristas una y otra vez.
Historia y usos
Edsger W. Dijkstra diseñó el algoritmo en 1956 para lucir un ordenador nuevo, el ARMAC en Amsterdam, buscando rutas entre ciudades neerlandesas, y lo publicó en 1959. La misma idea, con una cola más ingeniosa, funciona en los planificadores de rutas y en protocolos de enrutamiento de internet como OSPF e IS-IS, que calculan el camino más corto para los datos entre routers. El algoritmo A* añade una estimación de la distancia que falta, así puede dirigirse hacia el destino y revisar menos nodos.
Explóralo
Abre la aplicación y pulsa Paso. Los números de las aristas son sus longitudes, y el número de cada nodo es su distancia hasta ahora. Los nodos en la cola son azules, los definitivos verdes, y la cola bajo el grafo los muestra del más cercano al más lejano, con sus distancias. Fíjate en los momentos en que una distancia baja porque una ruta que parecía más larga resulta ser más corta, y elige un destino para ver cómo la búsqueda se detiene en cuanto el destino es definitivo.
Preguntas frecuentes
¿Cuál es la complejidad temporal del algoritmo de Dijkstra?
Depende de la cola de prioridad. Con una lista simple es O(V²) para V nodos; con un montículo binario, O((V + E) log V) para E aristas; con un montículo de Fibonacci, O(E + V log V), como demostraron Michael Fredman y Robert Tarjan en 1984.
¿Puede el algoritmo de Dijkstra manejar pesos negativos en las aristas?
No. Supone que la distancia de un nodo no puede mejorar una vez que el nodo es el más cercano de la cola, y una arista negativa puede romper eso. Usa el algoritmo de Bellman–Ford para grafos con aristas negativas.
¿Encuentra el algoritmo de Dijkstra el camino a cada nodo?
Sí. Ejecutado hasta el final, da la distancia más corta desde el origen hasta cada nodo alcanzable, y los nodos recordados forman un árbol de caminos más cortos. Parar antes, cuando el destino es definitivo, ahorra trabajo si solo hace falta un camino.
¿Qué relación hay entre el algoritmo de Dijkstra y A*?
El algoritmo A* es el algoritmo de Dijkstra con una pista: ordena la cola por la distancia hasta ahora más una estimación de la distancia que falta, como la distancia en línea recta en un mapa. Con una buena estimación encuentra el mismo camino más corto revisando muchos menos nodos.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Prueba el algoritmo de Dijkstra