Camino más corto de Dijkstra

Lo que cubre este capítulo

Hasta ahora, cada recorrido trataba una arista como un solo paso equivalente, y bajo ese supuesto el breadth-first search era el algoritmo de camino más corto: menos aristas significaba camino más corto. Los grafos reales rompen ese supuesto. Las carreteras tienen longitudes, los enlaces de red tienen latencias, los vuelos tienen tarifas: las aristas cargan pesos, y en cuanto lo hacen, el camino con menos aristas casi nunca es el más barato. Una sola arista de largo recorrido puede costar más que un rodeo de tres cortas. El algoritmo de Dijkstra es la solución, y la solución es mínima: cambia la cola simple del breadth-first search por una priority queue —el binary heap del capítulo de heaps— y expande siempre el nodo más cercano por peso total en lugar de por número de saltos. Este capítulo lo construye, lo ve asentar un grafo pequeño con pesos nodo por nodo, y lo muestra encontrando una ruta que cuesta un tercio de lo que costaría el camino de menos saltos que elegiría el breadth-first search.

Un poco de historia

Edsger Dijkstra ideó el algoritmo en 1956 y lo publicó en 1959, y la historia de su invención es famosa porque él mismo la contó sin adornos: lo resolvió en unos veinte minutos, mentalmente, tomando café con su prometida en la terraza de un café en Ámsterdam, como demostración del poder de ruteo de la computadora ARMAC. Evitó a propósito el lápiz y el papel para que la solución tuviera que ser lo bastante simple como para explicarla de viva voz, y por eso el algoritmo es tan limpio como es. La formulación original de 1959 no tenía heap: recorría todos los vértices en cada ronda para encontrar el más cercano, lo que daba $O(V^2)$, y esa forma sigue siendo la mejor opción para grafos densos. La versión $O((V+E)\log V)$ que casi todos entienden hoy por "Dijkstra" llegó después, cuando los binary heaps y luego los heaps de Fibonacci (Fredman y Tarjan, 1984) dieron una manera más rápida de extraer el mínimo una y otra vez. La idea central, eso sí, es enteramente de Dijkstra y enteramente de 1956: asienta con avaricia el nodo más cercano y, como los pesos son no negativos, su distancia es definitiva en el momento en que llegas a él.

La intuición

Guarda una distancia tentativa para cada nodo —cero para el origen, infinito para todo lo demás— y una priority queue ordenada por esa distancia. Saca repetidamente el nodo con la distancia tentativa más pequeña. Aquí está la afirmación clave: como todo peso de arista es no negativo, la distancia tentativa de ese nodo es ya su verdadera distancia más corta y nunca puede mejorar, así que lo "asentamos" de forma permanente. Cualquier otra ruta hacia él tendría que pasar por algún nodo que sigue en la cola, que está por lo menos igual de lejos, y luego avanzar todavía más, así que no puede ser más corta. Esto es exactamente el "el primer descubrimiento es el óptimo" del breadth-first search, nada más que medido en peso acumulado en lugar de en saltos.

Ya asentado un nodo, relajamos sus aristas: para cada vecino, revisamos si llegar a él pasando por el nodo recién asentado sale más barato que su distancia tentativa actual y, si es así, la bajamos y empujamos la entrada mejorada a la cola. La cola puede terminar guardando varias entradas del mismo nodo con distancias distintas; eso está bien y es más simple que intentar actualizar en el lugar: cuando sacamos una entrada obsoleta (una distancia peor que el valor ya asentado del nodo), simplemente la ignoramos. Todo el algoritmo es breadth-first search con la cola FIFO reemplazada por un min-heap, más el paso de relajación. Esa sola sustitución —de cola a priority queue— es la diferencia entre "el más cercano por saltos" y "el más barato por peso".

Complejidad: cómo escala

Con un binary heap, Dijkstra es $O((V + E)\log V)$: cada uno de los $V$ vértices se extrae una vez ($\log V$ cada uno) y cada una de las $E$ aristas puede disparar un push ($\log V$ cada uno). La versión de 1959 sin heap es $O(V^2)$ porque cada ronda recorre linealmente todos los vértices buscando el mínimo; gana solo cuando el grafo es lo bastante denso como para que $E \approx V^2$ y el factor $\log$ deje de ayudar. El espacio es $O(V)$ para los arrays de distancias y de padres, más el heap. Pero el número que importa para elegir Dijkstra no es su velocidad: es el costo del camino que encuentra comparado con el que te daría el breadth-first search sobre el mismo grafo con pesos:

En grafos con pesos de 400 vértices, el camino de menos saltos que elige el breadth-first search promedió alrededor de 25% más costo total que el camino más barato de Dijkstra, y ese es el caso promedio, donde los pesos aleatorios se compensan en parte. En el peor caso la brecha no tiene tope: en la animación de abajo el breadth-first search toma una sola arista directa de peso 10 cuando un rodeo de tres aristas cuesta apenas 3, una ruta más de tres veces más cara. De eso se trata todo el capítulo. En cuanto las aristas tienen pesos, el breadth-first search deja de responder la pregunta que en realidad estás haciendo, y Dijkstra es lo que sí la responde.

En qué es bueno y en qué no

Dijkstra es la herramienta correcta para caminos de menor costo desde un origen cuando los pesos de las aristas son no negativos, y eso cubre la mayoría de los problemas de caminos con pesos que te vas a encontrar: distancias de carretera, tiempos de viaje, latencias de red, costos de transmisión, secuencias de operaciones más baratas. Es eficiente, es una sola pasada limpia y, con un heap, escala a grafos grandes y dispersos. También generaliza: A* (un capítulo posterior) es Dijkstra más una heurística que lo dirige hacia una meta, y un recorrido con min-priority queue exactamente de esta forma es la base del árbol de expansión mínima de Prim.

Su requisito duro son los pesos no negativos. Una sola arista negativa puede hacer que asentar-al-sacar sea incorrecto, porque una ruta más barata podría llegar después de que un nodo ya se dio por definitivo; ese es el caso de Bellman-Ford del capítulo que sigue. Dijkstra además calcula distancias desde un origen; para distancias entre todos los pares, o lo corres desde cada vértice o te cambias a Floyd-Warshall. Y encuentra el camino más barato, que no siempre es el de menos saltos: si lo que te importa es el número de saltos (menos transbordos, menos intermediarios), el breadth-first search simple es a la vez correcto y más rápido, porque ahí el heap de Dijkstra es puro sobrecosto.

Los datos, o las entradas

La comparación corre sobre grafos aleatorios con pesos (pesos de arista de 1 a 20) y contrasta, para pares de nodos aleatorios, el costo total del camino más barato de Dijkstra contra el costo del camino de menos saltos que encuentra el breadth-first search, aislando el efecto de ignorar los pesos. La verificación de corrección confirma que las distancias de la versión con heap coinciden exactamente con la referencia confiable $O(V^2)$ en cientos de grafos, y que los pesos de las aristas de cada camino reconstruido suman el costo reportado. La animación corre Dijkstra sobre un grafo pequeño con pesos armado para que la arista directa sea una trampa: los números dentro de los nodos son sus distancias tentativas, así que puedes verlas caer conforme se relajan las aristas y congelarse cuando los nodos se asientan.

Constrúyelo, una función a la vez

El algoritmo central: un min-heap, asentar al sacar, relajar las aristas.

def dijkstra(adj, start):
    """Cheapest-cost distances from `start` over non-negative weighted edges. `adj[u]` is a
    list of (neighbor, weight). Keep a tentative distance for every node and a min-heap of
    (distance, node). Repeatedly pop the closest unsettled node — its distance is now final —
    and RELAX each outgoing edge: if going through u reaches v more cheaply, lower v's
    tentative distance and push the improved entry. O((V+E) log V) with a binary heap.
    Returns (dist, parent); parent lets you rebuild the actual path."""
    n = len(adj)
    dist = [float("inf")] * n
    parent = [-1] * n
    dist[start] = 0
    pq = [(0, start)]                       # (tentative distance, node)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                        # a stale, superseded entry — skip it
        for v, w in adj[u]:
            nd = d + w                       # cost to reach v via u
            if nd < dist[v]:                 # relaxation: found a cheaper way to v
                dist[v] = nd
                parent[v] = u
                heapq.heappush(pq, (nd, v))
    return dist, parent

Reconstruir el camino más barato real a partir de los apuntadores de padre:

def shortest_path(adj, start, target):
    """Rebuild the cheapest path start → target by walking parents back, then reversing.
    Returns (path, cost), or (None, inf) if the target is unreachable."""
    dist, parent = dijkstra(adj, start)
    if dist[target] == float("inf"):
        return None, float("inf")
    path, x = [], target
    while x != -1:
        path.append(x)
        x = parent[x]
    return path[::-1], dist[target]

Y la respuesta del breadth-first search a la misma pregunta, para mostrar por qué está mal en cuanto las aristas tienen peso:

def bfs_fewest_hops(adj, start, target):
    """BFS's answer to the same question, to show why it's the WRONG tool once edges have
    weights: it finds the path with the fewest EDGES, ignoring their cost. We then total the
    real weights along that fewest-hop path — usually more expensive than Dijkstra's."""
    from collections import deque
    n = len(adj)
    parent = [-1] * n
    seen = [False] * n
    seen[start] = True
    q = deque([start])
    while q:
        u = q.popleft()
        for v, _w in adj[u]:
            if not seen[v]:
                seen[v] = True
                parent[v] = u
                q.append(v)
    if not seen[target]:
        return None, float("inf")
    path, x = [], target
    while x != -1:
        path.append(x)
        x = parent[x]
    path.reverse()
    cost = 0
    wof = {(u, v): w for u in range(n) for v, w in adj[u]}
    for a, b in zip(path, path[1:]):
        cost += wof[(a, b)]
    return path, cost

Míralo funcionar

Aquí está Dijkstra sobre un grafo pequeño con pesos, arrancando en el nodo 0 (el destino es el nodo 6, hasta la derecha). El número dentro de cada nodo es su distancia tentativa actual: empieza en ∞ para todo menos el origen, y va cayendo conforme se relajan las aristas. Naranja es el nodo que se está asentando en ese paso; los nodos verdes ya están asentados (distancia definitiva); los azules están en la frontera (distancia tentativa finita, todavía mejorable); los oscuros están intactos. Los números grises sobre las aristas son sus pesos. Fíjate en el nodo 6: la arista directa 0→6 tiene peso 10, pero Dijkstra nunca la toma, porque asentar 1 y luego 3 revela que el rodeo 0→1→3→6 cuesta apenas 3. El camino más barato no es el de menos aristas: es el que la priority queue descubre persiguiendo siempre el total acumulado más pequeño.

El código completo

La pestaña "desde cero" es Dijkstra con heap, reconstrucción del camino y el contraste con BFS por saltos; la pestaña de librería es la referencia $O(V^2)$ contra la que se verifican las trazas, con las llamadas de networkx que realmente usarías anotadas arriba. Cambia entre ellas.

"""Dijkstra's algorithm — shortest paths in a graph whose edges have non-negative
weights. This is the moment the "every edge is one step" assumption of BFS breaks.
On a road map, a route with more turns can be shorter in miles; on a network, more hops
can mean less latency. When edges carry weights, "fewest edges" is no longer "cheapest,"
and BFS's shortest-path guarantee evaporates.

Dijkstra fixes it with one change: replace BFS's plain FIFO queue with a PRIORITY queue
(the binary heap from the heaps chapter). Instead of expanding the nearest node by
hop-count, always expand the nearest node by total WEIGHT so far. Because edge weights are
non-negative, the first time we pull a node off the priority queue we have its true
cheapest distance — the same "first discovery is optimal" guarantee as BFS, now measured
in cost rather than hops. That's the whole idea: BFS with a heap.
"""
import heapq


# region: dijkstra
def dijkstra(adj, start):
    """Cheapest-cost distances from `start` over non-negative weighted edges. `adj[u]` is a
    list of (neighbor, weight). Keep a tentative distance for every node and a min-heap of
    (distance, node). Repeatedly pop the closest unsettled node — its distance is now final —
    and RELAX each outgoing edge: if going through u reaches v more cheaply, lower v's
    tentative distance and push the improved entry. O((V+E) log V) with a binary heap.
    Returns (dist, parent); parent lets you rebuild the actual path."""
    n = len(adj)
    dist = [float("inf")] * n
    parent = [-1] * n
    dist[start] = 0
    pq = [(0, start)]                       # (tentative distance, node)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue                        # a stale, superseded entry — skip it
        for v, w in adj[u]:
            nd = d + w                       # cost to reach v via u
            if nd < dist[v]:                 # relaxation: found a cheaper way to v
                dist[v] = nd
                parent[v] = u
                heapq.heappush(pq, (nd, v))
    return dist, parent
# endregion


# region: shortest_path
def shortest_path(adj, start, target):
    """Rebuild the cheapest path start → target by walking parents back, then reversing.
    Returns (path, cost), or (None, inf) if the target is unreachable."""
    dist, parent = dijkstra(adj, start)
    if dist[target] == float("inf"):
        return None, float("inf")
    path, x = [], target
    while x != -1:
        path.append(x)
        x = parent[x]
    return path[::-1], dist[target]
# endregion


# region: bfs_hops
def bfs_fewest_hops(adj, start, target):
    """BFS's answer to the same question, to show why it's the WRONG tool once edges have
    weights: it finds the path with the fewest EDGES, ignoring their cost. We then total the
    real weights along that fewest-hop path — usually more expensive than Dijkstra's."""
    from collections import deque
    n = len(adj)
    parent = [-1] * n
    seen = [False] * n
    seen[start] = True
    q = deque([start])
    while q:
        u = q.popleft()
        for v, _w in adj[u]:
            if not seen[v]:
                seen[v] = True
                parent[v] = u
                q.append(v)
    if not seen[target]:
        return None, float("inf")
    path, x = [], target
    while x != -1:
        path.append(x)
        x = parent[x]
    path.reverse()
    cost = 0
    wof = {(u, v): w for u in range(n) for v, w in adj[u]}
    for a, b in zip(path, path[1:]):
        cost += wof[(a, b)]
    return path, cost
# endregion

"""The library counterpart. In practice you'd use networkx, whose `dijkstra_path` and
`single_source_dijkstra` are the same algorithm with a polished API:

    import networkx as nx
    G = nx.DiGraph()
    for u in range(n):
        for v, w in adj[u]:
            G.add_edge(u, v, weight=w)
    length, path = nx.single_source_dijkstra(G, source)   # dict of costs, dict of paths

networkx uses a binary heap exactly like impl.py. To keep this chapter's data
reproducible with the standard library alone, the trace generator checks our heap-based
Dijkstra against the simple O(V^2) reference below — the original 1959 formulation, which
scans for the closest unsettled node each round instead of using a heap. Same answers,
worse asymptotics; it's the ground truth, not the thing you'd ship.
"""


# region: reference
def dijkstra_dense(adj, start):
    """Dijkstra's original O(V^2) form: no heap. Each of V rounds linearly scans for the
    unsettled node with the smallest tentative distance, settles it, and relaxes its edges.
    Simple and correct — the trusted reference our heap version must match. Faster than the
    heap version only on very dense graphs (E close to V^2), where the heap's log factor
    stops paying off."""
    n = len(adj)
    dist = [float("inf")] * n
    dist[start] = 0
    settled = [False] * n
    for _ in range(n):
        u, best = -1, float("inf")
        for i in range(n):
            if not settled[i] and dist[i] < best:
                best, u = dist[i], i
        if u == -1:
            break                            # remaining nodes are unreachable
        settled[u] = True
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist
# endregion

Desde cero vs librería

La comparación que importa aquí no es nuestro Dijkstra contra el de una librería: calculan distancias idénticas, como lo confirma la verificación de corrección contra la referencia $O(V^2)$. Es Dijkstra contra el breadth-first search, y deja un punto sutil sobre la elección de algoritmos. BFS y Dijkstra responden preguntas distintas —menos saltos contra menor costo— y en un grafo sin pesos esas preguntas coinciden, que es por lo que BFS parecía "el" algoritmo de camino más corto hace dos capítulos. Los pesos separan las preguntas, y usar BFS en un grafo con pesos no es lento, es sencillamente incorrecto: optimiza la cantidad equivocada. La lección repite un tema del capítulo de BFS: emparejar el algoritmo con el problema no es solo cuestión de velocidad, es cuestión de qué cantidad estás minimizando. Dijkstra cuesta un factor $\log V$ más que BFS por el privilegio de respetar los pesos; en un grafo con pesos ese factor te compra corrección, y en uno sin pesos es puro desperdicio. En producción llamarías a single_source_dijkstra de networkx; construirlo una vez te muestra exactamente por qué está ahí el heap y exactamente cuándo los pesos lo vuelven necesario.

Dónde te lo vas a encontrar

Dijkstra es uno de los algoritmos más desplegados del mundo. Cada GPS y servicio de mapas —Google Maps, Waze, los routers de OpenStreetMap— corre Dijkstra o su pariente dirigido a meta A* sobre redes de carreteras ponderadas por distancia o tiempo de viaje. Los protocolos de ruteo de red calculan con él los caminos de menor costo: OSPF, la columna vertebral del ruteo IP dentro de redes grandes, es Dijkstra sobre un grafo de costos de enlace. Cotiza los itinerarios más baratos en búsquedas de vuelos y transporte, planea rutas de robots y de agentes de videojuegos, encuentra las secuencias de menor costo en investigación de operaciones, y aparece donde sea que "la manera más barata de llegar de aquí para allá" tenga pesos sobre las aristas. Sus parientes dirigido a meta y de árbol de expansión mínima —A* y Prim— son los siguientes capítulos, y ambos son este mismo recorrido con priority queue más una idea añadida.

Puntos clave

El algoritmo de Dijkstra encuentra los caminos de menor costo desde un origen sobre aristas con pesos no negativos, asentando repetidamente el nodo no asentado más cercano con una priority queue y relajando sus aristas, en $O((V+E)\log V)$. Es breadth-first search con la cola FIFO cambiada por un min-heap: el único cambio que convierte "menos saltos" en "menor costo", que en grafos con pesos es una respuesta distinta y normalmente mejor, un tercio del costo en el ejemplo amañado del capítulo. Su único requisito duro son los pesos no negativos, y esa razón es justo por la que existe el capítulo siguiente.

Bellman-Ford resuelve el caso que Dijkstra no puede: grafos con pesos de arista negativos, donde una ruta más barata puede aparecer después de que un nodo ya se habría asentado. Renuncia al ingenioso orden de asentar-una-sola-vez de Dijkstra y en su lugar relaja cada arista repetidamente: más lento, $O(VE)$, pero capaz de lidiar con negativos e incluso de detectar ciclos negativos, donde la noción misma de camino más corto se desmorona por completo.