Calculadora Bellman-Ford

Pseudocódigo

Bellman-Ford es el algoritmo de caminos mínimos que renuncia a la astucia a cambio de generalidad. No hay cola de prioridad ni decisión de orden, solo relajación repetida de todas las aristas.

BellmanFord(grafo, origen):
    para cada vértice v: dist[v] = infinito
    dist[origen] = 0

    repetir V - 1 veces:
        cambió = falso
        para cada arista (u, v, w):
            si dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                padre[v] = u
                cambió = verdadero
        si no cambió: salir        // salida anticipada

    // Una pasada extra detecta ciclos negativos
    para cada arista (u, v, w):
        si dist[u] + w < dist[v]:
            informar de ciclo negativo alcanzable

El invariante es que tras la pasada i, todo camino mínimo que use como mucho i aristas ya es correcto. Como un camino mínimo en un grafo sin ciclos negativos usa a lo sumo V - 1 aristas, V - 1 pasadas lo resuelven todo. Si una pasada V-ésima aún mejora algo, es que un camino se acorta sin límite, que es exactamente lo que significa un ciclo negativo.

Ejemplo resuelto, paso a paso

Ejecuta Bellman-Ford desde A sobre un grafo con una arista negativa que Dijkstra resolvería mal. Las aristas se relajan en el orden fijo que se indica.

Grafo de ejemplo: Aristas dirigidas A a B (4), A a C (5), B a C (-3) y C a D (2).

1. Inicializar. dist = A 0, B infinito, C infinito, D infinito.
2. Pasada 1. A a B fija dist[B] = 4. A a C fija dist[C] = 5. B a C ofrece 4 + (-3) = 1, mejor que 5, así que dist[C] = 1. C a D fija dist[D] = 1 + 2 = 3. Tras una pasada: A 0, B 4, C 1, D 3.
3. Pasada 2. Se vuelven a probar todas las aristas y nada mejora. Con la comprobación de salida anticipada el algoritmo se detiene aquí en lugar de ejecutar las pasadas restantes.
4. Comprobación de ciclo negativo. Un barrido más sobre las cuatro aristas no encuentra ninguna mejora, así que no hay ciclo negativo alcanzable desde A y las distancias son definitivas.
5. Por qué falla Dijkstra aquí. Dijkstra fijaría C a distancia 5 en cuanto C saliera de la cola de prioridad, porque supone que un nodo fijado ya no puede mejorar. La arista posterior B a C de peso -3 quedaría entonces ignorada, y Dijkstra informaría de dist[C] = 5 y dist[D] = 7 en lugar de los correctos 1 y 3.

Las distancias correctas son A 0, B 4, C 1, D 3. Una sola arista negativa basta para romper Dijkstra, y esa es la razón de que exista Bellman-Ford.

Complejidad y de dónde sale

Tiempo: O(VE) · Espacio: O(V)

El algoritmo realiza V - 1 pasadas y cada pasada relaja las E aristas una vez, lo que da O(VE). El espacio es una distancia y un padre por vértice, es decir O(V), llamativamente independiente de E. En un grafo denso donde E se acerca a V al cuadrado, el tiempo se aproxima a O(V al cubo), y por eso Bellman-Ford se reserva para casos donde realmente hay pesos negativos. La comprobación de salida anticipada, que detiene el proceso en cuanto una pasada no cambia nada, suele terminar en unas pocas pasadas sobre grafos reales aunque el peor caso siga siendo V - 1.

Cuándo usar Algoritmo de Bellman-Ford y cuándo no

Bellman-Ford es estrictamente más general que Dijkstra y estrictamente más lento. Elígelo solo cuando necesites de verdad lo que aporta.

Errores frecuentes

• Ejecutar solo V - 1 pasadas y darlo por terminado. Sin la pasada V-ésima adicional no puedes distinguir distancias correctas de distancias que siguen cayendo por un ciclo negativo. La pasada de detección no es contabilidad opcional, es lo que hace fiable la salida.
• Suponer que un ciclo negativo detectado afecta a todo el grafo. La pasada extra solo detecta ciclos alcanzables desde el origen. Un ciclo negativo en una componente inalcanzable es invisible y, a efectos de origen único, irrelevante. Si necesitas todos los ciclos negativos, ejecuta desde un origen virtual conectado a todos los vértices.
• Relajar desde vértices a distancia infinita. En lenguajes donde el infinito es un entero grande y no un flotante, dist[u] + w desborda y da la vuelta a negativo, creando mejoras fantasma. Protege la relajación comprobando que dist[u] no siga siendo infinito.
• Usarlo en grafos no negativos por precaución. En un grafo sin aristas negativas, Bellman-Ford calcula exactamente lo mismo que Dijkstra pero puede ser órdenes de magnitud más lento. La generalidad no es gratis.
• Esperar que existan caminos mínimos con un ciclo negativo. Cuando hay un ciclo negativo alcanzable no existe camino mínimo, no es que sea desconocido: siempre puedes dar otra vuelta al ciclo y bajar más. Informa del ciclo en lugar de devolver una distancia.

Preguntas frecuentes

¿Para qué sirve el algoritmo de Bellman-Ford?

Calcula caminos mínimos desde un único origen en grafos que pueden tener pesos negativos, y detecta ciclos negativos. En la práctica sostiene protocolos de enrutamiento por vector de distancia como RIP, la detección de arbitraje de divisas donde los tipos de cambio se convierten en logaritmos negativos, y problemas de planificación donde algunas transiciones aportan ganancia en lugar de coste.

¿Por qué usar Bellman-Ford en lugar de Dijkstra?

Porque Dijkstra es incorrecto con aristas negativas. Dijkstra fija un nodo de forma permanente cuando sale de la cola de prioridad, suponiendo que nada podrá mejorarlo después, y una arista negativa descubierta más tarde rompe ese supuesto. Bellman-Ford no adquiere ese compromiso, así que sigue siendo correcto a cambio de O(VE) en lugar de O((V + E) log V).

¿Cómo detecta Bellman-Ford los ciclos negativos?

Tras V - 1 pasadas de relajación, todo camino mínimo que pueda existir ya es definitivo, porque un camino simple tiene como mucho V - 1 aristas. Si una pasada más sobre todas las aristas aún mejora alguna distancia, esa mejora solo puede venir de un ciclo de peso total negativo alcanzable desde el origen.

¿Cuál es la complejidad temporal de Bellman-Ford?

O(VE) en tiempo y O(V) en espacio. Ejecuta V - 1 pasadas sobre las E aristas. Con la optimización de salida anticipada suele detenerse mucho antes en grafos reales, pero el peor caso no cambia. En grafos densos se acerca a O(V al cubo).

¿Puede Bellman-Ford manejar pesos negativos?

Sí, ese es todo su propósito, siempre que no haya un ciclo negativo alcanzable desde el origen. Con pesos negativos pero sin ciclo negativo devuelve caminos mínimos correctos. Con un ciclo negativo alcanzable no existe camino mínimo, y el algoritmo lo informa en lugar de devolver una distancia sin sentido.