Calculadora Dijkstra

Pseudocódigo

Dijkstra es un algoritmo voraz cuya corrección se apoya en una sola afirmación: el nodo pendiente más cercano ya no puede mejorarse después. Una cola de prioridad entrega ese nodo en O(log V).

Dijkstra(grafo, origen):
    para cada vértice v: dist[v] = infinito
    dist[origen] = 0
    cp = cola de prioridad con (0, origen)

    mientras cp no esté vacía:
        (d, u) = cp.extraerMínimo()
        si d > dist[u]: continuar     // entrada obsoleta
        para cada arista (u, v, w):
            si dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                padre[v] = u
                cp.insertar((dist[v], v))

La comprobación de entradas obsoletas importa. En lugar de reducir la clave dentro del montículo, algo que la mayoría de bibliotecas estándar no permite, lo habitual es insertar una entrada duplicada e ignorar cualquiera cuya distancia registrada ya no coincida. Esto se llama borrado perezoso, y es la razón de que la cola pueda contener hasta E entradas en lugar de V.

Ejemplo resuelto, paso a paso

Ejecuta Dijkstra desde A sobre un grafo con pesos donde la elección voraz da resultado, observando cómo crece el conjunto de nodos fijados.

Grafo de ejemplo: Aristas no dirigidas A-B (4), A-C (2), C-B (1), B-D (5) y C-D (8).

1. Inicializar. dist = A 0, B infinito, C infinito, D infinito. La cola contiene (0, A).
2. Fijar A en 0. Relaja A-B dando dist[B] = 4, y A-C dando dist[C] = 2. La cola contiene (2, C) y (4, B).
3. Fijar C en 2. C está más cerca que B, así que sale primero. Relaja C-B: 2 + 1 = 3, mejor que el 4 registrado, así que dist[B] = 3 y se inserta una nueva entrada (3, B). Relaja C-D: 2 + 8 = 10, así que dist[D] = 10.
4. Fijar B en 3. La entrada (3, B) sale antes que la obsoleta (4, B). Relaja B-D: 3 + 5 = 8, mejor que 10, así que dist[D] = 8.
5. Descartar la entrada obsoleta. Ahora sale la antigua entrada (4, B). Como 4 es mayor que dist[B], que es 3, se descarta sin reprocesar B. Aquí se ve el borrado perezoso en acción.
6. Fijar D en 8. No queda nada que mejorar. El algoritmo termina.

Las distancias finales son A 0, C 2, B 3, D 8, y el camino mínimo hasta D pasa por A, C, B y D. Fíjate en que la arista directa A-B de peso 4 nunca se usa: llegar por C cuesta 3. Fíjate también en que los nodos se fijan en orden de distancia 0, 2, 3, 8, que es exactamente la propiedad en la que se apoya el argumento voraz.

Complejidad y de dónde sale

Tiempo: O((V + E) log V) · Espacio: O(V)

Con un montículo binario, cada uno de los V vértices se extrae una vez a O(log V), y cada una de las E aristas puede provocar una inserción a O(log V), lo que da O((V + E) log V). Con borrado perezoso el montículo contiene hasta E entradas, así que la extracción es O(log E), pero como E es a lo sumo V al cuadrado, log E es como mucho 2 log V y la cota no cambia. Un montículo de Fibonacci mejora la cota teórica a O(E + V log V) porque reducir clave pasa a ser O(1) amortizado, aunque las constantes son lo bastante malas como para que en la práctica suelan ganar los montículos binarios. En un grafo denso, un simple recorrido de un vector para hallar el mínimo da O(V al cuadrado), que supera al montículo cuando E se acerca a V al cuadrado.

Cuándo usar Algoritmo de Dijkstra y cuándo no

Dijkstra es la opción por defecto para caminos mínimos con pesos. Lo que lo sustituye depende de cuál de sus supuestos rompa tu grafo.

Errores frecuentes

• Usarlo con pesos negativos. Este es el mal uso clásico. Dijkstra fija un nodo de forma permanente cuando sale de la cola; una arista negativa descubierta después lo habría mejorado, pero ya no se reconsidera. El resultado es silenciosamente incorrecto, no un error, lo que hace el fallo difícil de detectar. Usa Bellman-Ford.
• Olvidar la comprobación de entradas obsoletas. Sin la guarda `si d > dist[u]: continuar`, un vértice se reprocesa una vez por cada entrada en la cola. Sigue terminando y sigue dando respuestas correctas, pero vuelve a relajar aristas sin necesidad y puede degradarse mucho en grafos con muchas mejoras.
• Parar al ver el destino por primera vez. Alcanzar el destino durante una relajación no significa que su distancia sea definitiva. Solo lo es cuando el destino se extrae de la cola. Cortar al descubrirlo da respuestas erróneas; cortar al extraerlo es correcto y es una optimización legítima.
• Tratar las aristas de peso cero como un problema. Los pesos cero no dan ningún problema. Solo los pesos estrictamente negativos rompen el argumento, porque la demostración voraz necesita que las distancias no decrezcan a lo largo de un camino, y el cero preserva esa propiedad.
• Reconstruir todo el grafo para cada consulta. Una sola ejecución de Dijkstra da las distancias desde el origen a todos los nodos, no solo a uno. Si necesitas muchos orígenes, ese es otro problema: valora Floyd-Warshall o Johnson en lugar de ejecutar Dijkstra V veces sin pensarlo.

Preguntas frecuentes

¿Para qué sirve el algoritmo de Dijkstra?

Encuentra el camino más corto desde un origen a todos los demás nodos en un grafo con pesos no negativos. Sostiene la navegación GPS y el transporte público, protocolos de enrutamiento como OSPF e IS-IS, el análisis de latencia de redes y la búsqueda de rutas en videojuegos cuando no hay heurística disponible.

¿Cuál es la complejidad temporal del algoritmo de Dijkstra?

O((V + E) log V) con un montículo binario, que es la implementación estándar. Un montículo de Fibonacci la baja a O(E + V log V) en teoría, aunque las constantes suelen hacer más rápidos a los binarios. En grafos densos, recorrer un vector da O(V al cuadrado), que puede superar al montículo cuando E se acerca a V al cuadrado.

¿Por qué falla el algoritmo de Dijkstra con pesos negativos?

Porque fija cada nodo de forma permanente en cuanto tiene la menor distancia tentativa de la cola, suponiendo que ningún camino posterior podrá ser más corto. Una arista negativa viola ese supuesto: un camino descubierto después puede reducir una distancia ya fijada. Dijkstra nunca revisita nodos fijados, así que devuelve una respuesta incorrecta sin dar ningún error.

¿Cuál es la diferencia entre Dijkstra y A*?

A* es Dijkstra más una estimación heurística de la distancia restante hasta un destino concreto. Dijkstra expande nodos por distancia desde el origen y encuentra caminos hacia todo; A* expande por coste total estimado y se dirige a un único destino, explorando muchos menos nodos. Con una heurística nula, A* es exactamente Dijkstra.

¿Funciona el algoritmo de Dijkstra en grafos no dirigidos?

Sí. Una arista no dirigida son simplemente dos aristas dirigidas del mismo peso, así que el algoritmo se aplica sin cambios. El único requisito real es que ningún peso sea negativo.