Algoritmo de Bellman-Ford explicado: cómo funciona, código y complejidad

Qué problema resuelve Bellman-Ford

El algoritmo de Dijkstra es rápido, pero exige pesos de arista no negativos. Algunos problemas tienen pesos negativos de forma natural: un reembolso, una ganancia en un cambio de divisas o un coste de energía que puede bajar de cero. Bellman-Ford trata estos grafos correctamente y además te avisa cuando no existe un camino más corto por culpa de un ciclo negativo, un bucle que podrías recorrer sin fin para reducir el coste una y otra vez.

El algoritmo recibe el nombre de Richard Bellman y Lester Ford Jr., que publicaron versiones del mismo en la década de 1950.

La idea en palabras sencillas

1. Asigna distancia 0 al nodo inicial e infinito a todos los demás.
2. Repite V − 1 veces: para cada arista u → v de peso w, si dist[u] + w < dist[v], actualiza dist[v].
3. Haz una pasada más sobre todas las aristas. Si alguna distancia aún mejora, informa de un ciclo negativo.

¿Por qué V − 1 rondas? Un camino más corto sin ciclos usa como máximo V − 1 aristas. Tras la ronda k, todo nodo cuyo camino más corto tiene como máximo k aristas ya tiene su distancia correcta, de modo que V − 1 rondas cubren todos los caminos simples.

Ejemplo resuelto, paso a paso

Grafo dirigido con 4 nodos y las aristas S→A (4), S→B (5), B→A (−3), A→C (3). Las aristas se procesan en este orden en cada ronda.

En la ronda 1, A pasa primero a valer 4 por S→A y luego mejora a 2 por B→A, y C usa el valor mejorado. El algoritmo de Dijkstra habría dado A por definitivo con 4 antes de mirar B, que es justo el error que causa una arista negativa.

Implementación en Python

Bellman-Ford trabaja sobre una lista simple de aristas, lo que lo hace corto de escribir:

def bellman_ford(nodes, edges, start):
    """edges: list of (u, v, weight). Returns dist, or raises on a negative cycle."""
    INF = float("inf")
    dist = {n: INF for n in nodes}
    dist[start] = 0
    for _ in range(len(nodes) - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                         # already optimal
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            raise ValueError("graph contains a negative cycle")
    return dist
nodes = ["S", "A", "B", "C"]
edges = [("S", "A", 4), ("S", "B", 5), ("B", "A", -3), ("A", "C", 3)]
print(bellman_ford(nodes, edges, "S"))  # {'S': 0, 'A': 2, 'B': 5, 'C': 5}

Al añadir una arista C → B con peso −6 se crea el ciclo B → A → C → B con peso total −3 + 3 − 6 = −6, así que la pasada extra lo encuentra:

try:
    bellman_ford(nodes, edges + [("C", "B", -6)], "S")
except ValueError as e:
    print(e)  # graph contains a negative cycle

La comprobación dist[u] != INF omite las aristas que salen de nodos aún no alcanzados. En Python, float("inf") + w sigue siendo infinito, así que la comprobación sobre todo ahorra trabajo. En lenguajes que usan un entero grande como infinito, evita desbordamientos y actualizaciones falsas.

Complejidad temporal y espacial

En un grafo de 1000 nodos y 10 000 aristas son hasta unos 10 millones de relajaciones, así que Dijkstra es mucho más rápido cuando todos los pesos son no negativos.

Variantes y errores comunes

• Salida anticipada: detente cuando una ronda completa no cambie nada. Es seguro y en la práctica suele acelerar mucho el algoritmo.
• SPFA (shortest path faster algorithm): vuelve a relajar solo las aristas que salen de los nodos cuya distancia cambió, usando una cola. Suele ser rápido, pero tiene el mismo peor caso O(V × E).
• Caminos con límite de saltos: ejecutar exactamente k rondas, usando una copia de las distancias de la ronda anterior, da el camino más barato con como máximo k aristas. Así se resuelve "vuelos más baratos con k escalas".
• Encontrar el ciclo en sí: guarda un mapa de padres; cuando la pasada extra actualice el nodo v, sigue los padres V veces para caer dentro del ciclo y luego recórrelo hasta volver al mismo nodo.

Cuándo usarlo y usos en el mundo real

• Usa Bellman-Ford cuando los pesos puedan ser negativos o cuando debas detectar ciclos negativos. En los demás casos, prefiere Dijkstra.
• Los protocolos de enrutamiento por vector de distancias, como RIP, usan la idea distribuida de Bellman-Ford: cada router actualiza repetidamente sus estimaciones de distancia a partir de las de sus vecinos.
• Arbitraje de divisas: con pesos iguales a -log(rate), un ciclo negativo es una secuencia de cambios que termina con más dinero del que se tenía al empezar.
• El algoritmo de Johnson ejecuta Bellman-Ford una vez para reponderar un grafo y poder usar después Dijkstra desde cada nodo para obtener los caminos más cortos entre todos los pares.
• Las restricciones de diferencia (sistemas de desigualdades como x - y <= c) se pueden resolver como caminos más cortos; un ciclo negativo significa que no existe solución.