Bellman-Ford

De qué trata este capítulo

El algoritmo de Dijkstra tenía un requisito duro: nada de pesos negativos en las aristas. Bellman-Ford es al que recurres cuando ese requisito no se puede cumplir — cuando algunas aristas hacen las cosas más baratas, como en un grafo de tipos de cambio, un problema de calendarización con bonificaciones, o cualquier sistema donde un movimiento puede devolverte costo. Dijkstra se rompe con los negativos porque cierra cada nodo la primera vez que lo alcanza, confiando en que nada más barato puede llegar después, y una arista negativa viola justo esa confianza. Bellman-Ford abandona el orden astuto de cerrar-una-sola-vez y hace algo casi vergonzosamente simple: relaja todas las aristas del grafo, y luego otra vez, y otra, V−1 veces. Es más lento — O(V·E) — pero aguanta pesos negativos, y con una pasada extra detecta un ciclo negativo, la situación donde "camino más corto" deja de significar algo porque podrías dar vueltas para siempre abaratando. Este capítulo lo construye, ve cómo las distancias se propagan pasada por pasada, y mide qué tan seguido Dijkstra devuelve calladito una respuesta equivocada en cuanto aparecen aristas negativas.

Un poco de historia

El algoritmo lleva los nombres de Richard Bellman, quien lo publicó en 1958, y de Lester Ford Jr., quien lo describió en 1956, con Edward Moore llegando a él de forma independiente en 1959 — así que a veces se le llama Bellman-Ford-Moore. Bellman fue la misma figura que acuñó el término "programación dinámica" unos años antes, y Bellman-Ford es en realidad programación dinámica sobre grafos: la distancia más corta a un nodo usando a lo más $k$ aristas se construye a partir de las distancias más cortas usando a lo más $k-1$ aristas, y cada pasada avanza $k$ en uno. Ese encuadre — la respuesta para $k$ aristas depende de la respuesta para $k-1$ — es la razón por la que el algoritmo se siente tan distinto del cierre voraz de Dijkstra y por la que cae en la misma familia intelectual que los capítulos de programación dinámica más adelante en este libro. Su uso práctico más duradero fue el ruteo por vector de distancia: el protocolo de ruteo original de ARPANET y después RIP hacían que cada router compartiera repetidamente sus estimaciones de distancia con sus vecinos y relajara — un Bellman-Ford distribuido corriendo a lo largo de toda una red.

La intuición

Olvídate de ser astuto sobre cuál nodo procesar a continuación. Bellman-Ford considera todas las aristas por igual y simplemente relaja cada una de ellas: para cada arista $u \to v$ de peso $w$, si llegar a $v$ pasando por $u$ es más barato que la estimación actual de $v$, bájala. Haz eso para toda la lista de aristas y habrás completado una pasada. La garantía después de una pasada es modesta pero precisa: todo nodo cuyo camino más corto usa una sola arista ya tiene su distancia final. Después de dos pasadas, todo nodo alcanzable en a lo más dos aristas queda final. Después de $k$ pasadas, todo lo alcanzable en a lo más $k$ aristas. Como un camino más corto en un grafo sin ciclos negativos visita a lo más $V-1$ aristas (más que eso repetiría un nodo, y repetir un nodo en un camino más corto solo ayuda si el ciclo es negativo), $V-1$ pasadas dejan todo resuelto.

La corrección no depende para nada del signo de los pesos — la relajación solo baja una estimación hacia la verdad, y después de suficientes pasadas cada camino más corto ya tuvo sus aristas relajadas en orden. Por eso los negativos aquí no son problema donde arruinaban a Dijkstra: Bellman-Ford nunca congela un nodo, así que una ruta más barata descubierta en una pasada posterior siempre sigue siendo bienvenida. Y te regala la detección de ciclos. Después de $V-1$ pasadas todo debería estar final, así que si una $V$-ésima pasada todavía puede relajar alguna arista, tiene que haber un ciclo negativo alimentándola — un ciclo cuyo peso total es negativo, alrededor del cual las distancias caen sin límite. Entonces "camino más corto" queda indefinido, y la respuesta honesta es reportar el ciclo en lugar de un número.

Complejidad: cómo escala

Cada pasada relaja las $E$ aristas en $O(E)$, y hay $V-1$ pasadas, así que Bellman-Ford es $O(V \cdot E)$ — en un grafo denso eso es $O(V^3)$, notoriamente más lento que el $O((V+E)\log V)$ de Dijkstra. El espacio es $O(V)$. Una optimización común corta temprano si una pasada no cambia nada (las distancias ya convergieron), cosa que la implementación hace, pero el peor caso sigue en pie. Pagas ese factor extra de $V$ por una sola cosa: corrección en presencia de pesos negativos. El duelo mide exactamente qué estás comprando — qué tan seguido el algoritmo más rápido, Dijkstra, devuelve una distancia equivocada conforme las aristas negativas se vuelven más comunes:

Sin aristas negativas los dos coinciden perfectamente — Dijkstra es correcto y deberías usarlo. Pero en cuanto aparecen negativos, el atajo de cerrar-una-sola-vez de Dijkstra empieza a devolver distancias equivocadas: con 30% de aristas negativas se equivocó en cerca del 5% de las distancias de los nodos, en silencio, sin error ni advertencia. Bellman-Ford estuvo correcto en todas. Ese es el trato en una frase: Dijkstra es más rápido pero solo válido en grafos no negativos, y en los negativos no falla con estruendo — nada más miente. Bellman-Ford es el algoritmo más lento que dice la verdad, y detecta el único caso (un ciclo negativo) donde no hay verdad que decir.

En qué es bueno y en qué no

Bellman-Ford es la herramienta correcta siempre que los pesos de las aristas puedan ser negativos y aun así necesites caminos más cortos — detección de arbitraje de divisas, sistemas de restricciones de diferencia (cada "x − y ≤ c" es una arista), ruteo por vector de distancia donde corre distribuido a lo largo de una red, y cualquier problema que puedas codificar con movimientos de costo negativo. Su capacidad de detectar ciclos suele ser la verdadera razón para usarlo: reportar "no hay camino más corto, aquí está un ciclo negativo" muchas veces vale más que una distancia, porque en arbitraje o en resolución de restricciones el ciclo es la respuesta. También es simple de implementar y de razonar, al ser nada más relajación repetida sin cola de prioridad.

Donde pierde es en velocidad sobre grafos no negativos, donde su sobrecosto de factor $V$ es puro desperdicio — ahí usa Dijkstra. Es de origen único, igual que Dijkstra; para caminos más cortos entre todos los pares con negativos usarías Floyd-Warshall (el siguiente capítulo) o el algoritmo de Johnson. Y en grafos muy grandes el costo $O(VE)$ puede ser prohibitivo, que es por lo que los sistemas de ruteo reales le montan optimizaciones encima (la variante SPFA basada en cola, la terminación temprana) o evitan los pesos negativos por construcción.

Los datos, o las entradas

El duelo corre sobre grafos dirigidos acíclicos aleatorios — un DAG nunca puede contener un ciclo, así que nunca uno negativo, lo que nos deja hacer negativa una fracción grande de las aristas manteniendo bien definido el problema del camino más corto. Para cada uno, compara las distancias de Dijkstra contra las de Bellman-Ford y cuenta en cuántos nodos se equivoca Dijkstra. La corrección se contraverifica de dos maneras independientes: contra Dijkstra en grafos no negativos (donde ambos tienen la razón), y contra Floyd-Warshall (el método de todos-los-pares del siguiente capítulo, que no le debe nada al enfoque de Bellman-Ford) en grafos con aristas negativas — más cientos de grafos con un ciclo negativo plantado a propósito para confirmar la detección. La animación corre Bellman-Ford sobre un grafo pequeño con una arista negativa (dibujada en rojo); los números dentro de los nodos son sus estimaciones de distancia actuales.

Constrúyelo, una función a la vez

El algoritmo completo — relajar todas las aristas V−1 veces, y luego una pasada para detectar un ciclo negativo:

def bellman_ford(n, edges, start):
    """Shortest-path distances from `start`, edges given as (u, v, w) with any sign.
    Relax all E edges, V-1 times: after pass k, every node reachable by a shortest path of
    <= k edges has its final distance, and a shortest path has at most V-1 edges. Returns
    (dist, parent, has_negative_cycle). If a Vth relaxation still improves something, a
    negative cycle is reachable and the distances below it are meaningless."""
    dist = [float("inf")] * n
    parent = [-1] * n
    dist[start] = 0
    for _ in range(n - 1):                      # V-1 passes
        changed = False
        for u, v, w in edges:
            if dist[u] != float("inf") and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w            # relaxation — the same primitive as Dijkstra
                parent[v] = u
                changed = True
        if not changed:
            break                                # converged early: no pass changed anything
    # one more pass: any further improvement proves a reachable negative cycle
    has_neg_cycle = any(
        dist[u] != float("inf") and dist[u] + w < dist[v] for u, v, w in edges
    )
    return dist, parent, has_neg_cycle

Reconstruir el camino, con los dos modos de falla hechos explícitos:

def shortest_path(n, edges, start, target):
    """Rebuild the cheapest path start → target from the parent pointers. Returns
    (path, cost), or (None, inf) if unreachable, or (None, -inf) if a negative cycle makes
    the distance unbounded below."""
    dist, parent, neg = bellman_ford(n, edges, start)
    if neg:
        return None, float("-inf")
    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]

Míralo trabajar

Aquí está Bellman-Ford sobre un grafo de cinco nodos, desde el nodo 0. El número dentro de cada nodo es su estimación de distancia actual — ∞ hasta que la onda lo alcanza — y la arista roja (2→1, peso −3) es la negativa que vuelve a este grafo una trampa para Dijkstra. Mira las pasadas: en la pasada 1 las estimaciones se esparcen en el orden de la lista de aristas, y el nodo 1 primero recibe distancia 4 por la arista directa 0→1; pero luego la arista negativa 2→1 la relaja hasta 2, y en la pasada 2 esa mejora se propaga hacia los nodos 3 y 4. Dijkstra habría cerrado el nodo 1 en 4 y nunca lo habría vuelto a visitar. Bellman-Ford, relajando todo en cada pasada, atrapa la ruta más barata y la propaga — y una pasada final sin cambios confirma que las distancias son definitivas:

El código completo

La pestaña "desde cero" es Bellman-Ford con detección de ciclos y reconstrucción de camino; la pestaña de librería es el Dijkstra de cerrar-una-sola-vez contra el que se corrió — el algoritmo rápido que aquí da la respuesta equivocada — con la llamada a networkx que usarías en producción anotada arriba. Alterna entre las dos.

"""Bellman-Ford — shortest paths from a source when edges may have NEGATIVE weights,
the case Dijkstra can't handle. Negative edges are not exotic: a graph of currency
trades, a game where some moves refund cost, a scheduling problem with rebates — anywhere
"traversing this edge makes things cheaper" is meaningful.

Dijkstra fails on negatives because it settles a node the first time the heap pops it,
trusting that no cheaper route can arrive later — which a negative edge can violate.
Bellman-Ford gives up that clever settle-once order entirely. It just relaxes EVERY edge,
V-1 times over. Each full pass guarantees every shortest path of one more edge is found,
and since a shortest path visits at most V-1 edges, V-1 passes suffice. It's slower —
O(V·E) instead of O((V+E) log V) — but it copes with negatives, and one extra pass detects
a negative cycle, where "shortest path" stops meaning anything (you could loop forever
getting cheaper).
"""


# region: bellman_ford
def bellman_ford(n, edges, start):
    """Shortest-path distances from `start`, edges given as (u, v, w) with any sign.
    Relax all E edges, V-1 times: after pass k, every node reachable by a shortest path of
    <= k edges has its final distance, and a shortest path has at most V-1 edges. Returns
    (dist, parent, has_negative_cycle). If a Vth relaxation still improves something, a
    negative cycle is reachable and the distances below it are meaningless."""
    dist = [float("inf")] * n
    parent = [-1] * n
    dist[start] = 0
    for _ in range(n - 1):                      # V-1 passes
        changed = False
        for u, v, w in edges:
            if dist[u] != float("inf") and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w            # relaxation — the same primitive as Dijkstra
                parent[v] = u
                changed = True
        if not changed:
            break                                # converged early: no pass changed anything
    # one more pass: any further improvement proves a reachable negative cycle
    has_neg_cycle = any(
        dist[u] != float("inf") and dist[u] + w < dist[v] for u, v, w in edges
    )
    return dist, parent, has_neg_cycle
# endregion


# region: shortest_path
def shortest_path(n, edges, start, target):
    """Rebuild the cheapest path start → target from the parent pointers. Returns
    (path, cost), or (None, inf) if unreachable, or (None, -inf) if a negative cycle makes
    the distance unbounded below."""
    dist, parent, neg = bellman_ford(n, edges, start)
    if neg:
        return None, float("-inf")
    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

"""The library counterpart and the contrast. In production you'd call
networkx.single_source_bellman_ford, which is the same algorithm with negative-cycle
detection built in:

    import networkx as nx
    G = nx.DiGraph()
    for u, v, w in edges:
        G.add_edge(u, v, weight=w)
    length, path = nx.single_source_bellman_ford(G, source)   # raises on a negative cycle

But the more instructive comparison is against DIJKSTRA — the faster algorithm that gets
the wrong answer here. `dijkstra` below is the heap version from the previous chapter; the
trace generator runs it on graphs with negative edges to show exactly where and by how
much it goes wrong, which is the whole reason Bellman-Ford exists.
"""
import heapq


# region: dijkstra
def dijkstra(n, edges, start):
    """Dijkstra's defining optimization made explicit: SETTLE each node the first time it's
    popped and never revisit it. That's exactly what makes it fast (each node processed once)
    and exactly what makes it WRONG on negative edges — once a node is settled its distance is
    frozen, so a cheaper route discovered later is silently ignored. Valid only for
    non-negative weights; here it's the cautionary contrast to Bellman-Ford."""
    adj = [[] for _ in range(n)]
    for u, v, w in edges:
        adj[u].append((v, w))
    dist = [float("inf")] * n
    dist[start] = 0
    settled = [False] * n
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if settled[u]:
            continue
        settled[u] = True                    # frozen from here on — the source of the error
        for v, w in adj[u]:
            if not settled[v] and d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(pq, (d + w, v))
    return dist
# endregion

Desde cero contra la librería

La comparación instructiva no es nuestro Bellman-Ford contra el de una librería, sino Bellman-Ford contra Dijkstra — dos algoritmos de camino más corto donde el más rápido está equivocado en silencio justo en las entradas para las que el más lento fue construido. Ese es un modo de falla distinto al de la mayoría de los duelos de este libro. Normalmente la herramienta equivocada es más lenta o usa más memoria; aquí Dijkstra es más rápido y devuelve una respuesta de apariencia plausible que simplemente es incorrecta, sin crash y sin advertencia. La lección es sobre precondiciones: la garantía de un algoritmo vale tanto como sus suposiciones, y la suposición de Dijkstra — pesos no negativos — es fácil de violar sin darte cuenta. Saber por qué Dijkstra necesita la no negatividad (cierra los nodos una sola vez) te dice exactamente cuándo tienes que bajarle a Bellman-Ford y pagar el factor de $V$. En producción usarías bellman_ford o single_source_bellman_ford de networkx; construirlo tú mismo es lo que convierte "Dijkstra dio la distancia equivocada" en una consecuencia predecible en vez de un bug desconcertante.

Dónde te lo vas a encontrar

La aplicación estelar de Bellman-Ford es el ruteo de redes: los protocolos de vector de distancia — el algoritmo original de ARPANET, RIP, y el BGP de vector de camino que cose el internet entero — son Bellman-Ford distribuido, con cada router relajando las estimaciones de distancia que comparten sus vecinos. Detecta arbitraje en mercados de divisas y de criptomonedas, donde un ciclo negativo en el grafo de log-tasas es un ciclo de ganancia sin riesgo. Resuelve sistemas de restricciones de diferencia en calendarizadores y compiladores (cada restricción es una arista, la factibilidad es la ausencia de un ciclo negativo). Está por debajo del algoritmo de todos-los-pares de Johnson, que usa una pasada de Bellman-Ford para repesar un grafo y que Dijkstra pueda correr con seguridad desde cada nodo. Y es la respuesta estándar de salón de clases a "caminos más cortos con aristas negativas", porque su lógica es transparente. Dondequiera que aparezcan negativos o haya que encontrar un ciclo negativo, Bellman-Ford es la herramienta.

Puntos clave

Bellman-Ford encuentra los caminos más cortos desde un origen incluso con pesos de arista negativos, relajando todas las aristas $V-1$ veces — programación dinámica sobre grafos, donde la pasada $k$ deja final toda distancia alcanzable en $k$ aristas — en $O(V \cdot E)$. Nunca cierra un nodo, así que tolera las aristas negativas que rompen el atajo de cerrar-una-sola-vez de Dijkstra, y una $V$-ésima pasada detecta los ciclos negativos donde los caminos más cortos dejan de existir. Es la contraparte lenta y veraz de Dijkstra: usa Dijkstra cuando los pesos son no negativos, bájale a Bellman-Ford cuando no lo son.

Los dos algoritmos que llevamos calculan distancias desde un solo origen. El siguiente capítulo pide todas de golpe — la distancia más corta entre cada par de nodos — y la responde con Floyd-Warshall, un triple ciclo asombrosamente corto que es programación dinámica de otro sabor, maneja aristas negativas igual que Bellman-Ford, y calcula la matriz de distancias completa en $O(V^3)$.