Algoritmo de Dijkstra explicado: cómo funciona, código y complejidad

Qué problema resuelve el algoritmo de Dijkstra

La búsqueda en anchura encuentra el camino con menos aristas, pero las carreteras, los enlaces de red y los vuelos tienen longitudes, costes o retrasos distintos. El algoritmo de Dijkstra resuelve el problema del camino más corto desde un único origen en estos grafos con pesos: dado un nodo inicial, halla el coste total mínimo para llegar a cada uno de los demás nodos y el camino que lo consigue.

Edsger W. Dijkstra publicó el algoritmo en 1959 en el artículo "A note on two problems in connexion with graphs".

La idea en palabras sencillas

1. Asigna distancia 0 al nodo inicial e infinito a todas las demás.
2. Elige el nodo sin terminar con la menor distancia. Su distancia ya es definitiva.
3. Relaja cada arista saliente u → v de peso w: si dist[u] + w < dist[v], asigna dist[v] = dist[u] + w y recuerda u como el padre de v.
4. Repite los pasos 2 y 3 hasta que todos los nodos alcanzables estén terminados.

¿Por qué es definitiva la menor distancia? Cualquier otra ruta hacia ese nodo tendría que pasar por un nodo cuya distancia ya es al menos igual de grande y, con pesos no negativos, las aristas restantes solo pueden sumar coste.

Ejemplo resuelto, paso a paso

Grafo dirigido con las aristas A→B (4), A→C (1), C→B (2), B→D (1), C→D (5), D→E (3). Empieza en A.

B recibe primero la distancia 4 por la arista directa y luego mejora a 3 pasando por C. El camino más corto hasta E es A → C → B → D → E con un coste total de 1 + 2 + 1 + 3 = 7.

Implementación en Python con heapq

El módulo heapq de Python ofrece un montículo binario de mínimos. En lugar de una operación de "disminuir clave", inserta un nuevo par (distance, node) cada vez que una distancia mejora y descarta los pares obsoletos cuando se extraen. Esto se llama eliminación perezosa.

import heapq
def dijkstra(graph, start):
    dist = {start: 0}
    parent = {start: None}
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                      # outdated entry
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                parent[v] = u
                heapq.heappush(heap, (nd, v))
    return dist, parent
graph = {
    "A": [("B", 4), ("C", 1)], "B": [("D", 1)],
    "C": [("B", 2), ("D", 5)], "D": [("E", 3)], "E": [],
}
dist, parent = dijkstra(graph, "A")
print(dist)  # {'A': 0, 'B': 3, 'C': 1, 'D': 4, 'E': 7}

Para obtener el camino hasta un destino, sigue los enlaces a los padres hacia atrás hasta el inicio:

def path_to(parent, target):
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]
print(path_to(parent, "E"))  # ['A', 'C', 'B', 'D', 'E']

Si solo necesitas la distancia a un destino, puedes detenerte en cuanto ese destino sale del montículo: su distancia ya es definitiva en ese momento.

Complejidad temporal y espacial

El espacio es O(V + E) para el grafo, los mapas de distancias y padres, y el montículo.

Variantes y errores comunes

• Olvidar la comprobación if d > dist[u]: continue no es incorrecto, pero hace que el algoritmo procese entradas obsoletas y puede ralentizarlo mucho.
• Insertar solo el nodo en lugar de (distance, node) hace que el orden del montículo no tenga sentido.
• Si los nodos son objetos que no se pueden comparar, los empates de distancia hacen que heapq compare los nodos y lance TypeError. Inserta (distance, counter, node) con un contador único.
• La búsqueda A* es Dijkstra con una heurística sumada a la prioridad; explora menos nodos cuando tienes una buena estimación de la distancia restante.
• Dijkstra bidireccional se ejecuta desde el origen y desde el destino a la vez y se detiene cuando las búsquedas se encuentran.

Cuándo usarlo y usos en el mundo real

• Enrutamiento: los protocolos de enrutamiento de estado de enlace, como OSPF e IS-IS, ejecutan un cálculo del camino más corto primero (SPF) basado en el algoritmo de Dijkstra.
• Mapas y navegación, donde los sistemas de producción añaden preprocesamiento sobre una búsqueda de tipo Dijkstra.
• Problemas de entrevista: tiempo de retraso de red, vuelos más baratos (con límite de escalas), camino de mínimo esfuerzo en una cuadrícula y cualquier pregunta de "coste total mínimo" sobre un grafo.