Tema

Algoritmo de Dijkstra

Algoritmos
Nivel intermedio
Con simulador interactivo

El algoritmo de Dijkstra halla el camino de menor peso desde un origen hasta todos los vértices de un grafo con pesos no negativos.

Nombre en inglés

Dijkstra shortest path algorithm

Intuición

Se comporta como un recorrido en anchura donde la cola respeta la distancia acumulada en lugar del número de saltos. Conviene imaginar agua que sale del origen por tubos de distinta longitud: El vértice que se moja antes queda fijado para siempre, y esa garantía se apoya en que ningún tramo posterior puede restar distancia, condición que los pesos negativos rompen.

Fórmula

relajacion: d[v] = min(d[v], d[u] + peso(u, v)) ; coste O((V + E) log V) con monticulo binario

Ejemplo resuelto

Sea un grafo con aristas de A a B de peso 1, de A a C de peso 4 y de B a C de peso 2. Desde A se fija primero B con distancia 1, y desde B se relaja C hasta 1 más 2, es decir 3, mejor que la arista directa de peso 4. El resultado final es distancia 1 hasta B y distancia 3 hasta C.

Errores frecuentes

Usar Dijkstra con pesos negativos: Una vez fijado un vértice ya no se revisa, y una arista negativa posterior podría mejorarlo, motivo por el cual se recurre a Bellman Ford.
Actualizar la cola de prioridad sin marcar las entradas obsoletas: La implementación habitual inserta duplicados y los descarta al extraer un vértice que ya está fijado.
Confundir el peso de la arista con la distancia acumulada: La cola ordena por distancia desde el origen y no por el peso del último tramo.

Ejercicio

En un grafo con aristas de S a A de peso 2, de S a B de peso 5 y de A a B de peso 1, ¿cuál es la distancia mínima de S a B?

Ver la solución

El camino directo cuesta 5, mientras que el camino que pasa por A cuesta 2 más 1.