El algoritmo de Bellman–Ford
Algunos problemas de camino más corto tienen aristas que abaratan un camino: un reembolso, un tramo cuesta abajo, un tipo de cambio a tu favor. El algoritmo de Dijkstra no puede con ellas. El algoritmo de Bellman–Ford sí, porque cambia astucia por paciencia.
La idea
Todo algoritmo de camino más corto se basa en un solo movimiento, relajar una arista: si ir hasta u y luego por la arista u → v es más corto que el mejor camino conocido hasta v, se usa. El algoritmo de Dijkstra relaja cada arista una vez, en un orden astuto que solo funciona si ninguna arista es negativa. Bellman–Ford no supone nada de eso. Relaja cada arista, en cualquier orden fijo, una y otra vez, hasta que las distancias dejan de cambiar.
Paso a paso
Da al origen distancia 0 y a todos los demás nodos infinito. Repite n − 1 veces, para n nodos: recorre cada arista u → v y relájala si u tiene distancia. Para antes si una pasada entera no cambia nada. Luego haz una pasada más. Si alguna arista aún se puede relajar, desde el origen se llega a un ciclo con total negativo; si no, cada distancia es la más corta, y los nodos recordados dan los caminos.
Un ejemplo
Toma las aristas de un solo sentido A → B de longitud 4, A → C 5, B → D 2 y C → B −3, revisadas en ese orden, desde A. La pasada 1 da B 4, C 5 y D 6, y luego C → B baja B a 5 − 3 = 2. La pasada 2 baja D a 2 + 2 = 4. La pasada 3 no cambia nada, así que la respuesta es B 2, C 5, D 4. El algoritmo de Dijkstra habría hecho definitivos B en 4 y D en 6, antes de ver la arista negativa. Añade una arista D → C de longitud −4, y el ciclo C → B → D → C suma −5: cada pasada vuelve a bajar las distancias, y la pasada de comprobación lo detecta.
Por qué bastan n − 1 pasadas
Un camino más corto, cuando existe, nunca repite un nodo, así que tiene como mucho n − 1 aristas. Relajar cada arista en una pasada alarga una arista más cada camino más corto ya conocido correctamente, sea cual sea el orden de las aristas. Así, tras la pasada k son correctos todos los caminos más cortos de hasta k aristas, y tras n − 1 pasadas, todos. El orden aún importa para la velocidad: con un buen orden puede terminar en una o dos pasadas.
Historia y usos
Alfonso Shimbel describió el método en 1955, Lester Ford Jr. en 1956, Edward F. Moore en 1957 y Richard Bellman en 1958; lleva el nombre de dos de ellos, Bellman y Ford. Cada router puede hacer sus pasadas por su cuenta, y por eso es la base de protocolos de enrutamiento por vector de distancias como RIP. En finanzas, tomar el logaritmo negativo de los tipos de cambio convierte una ronda rentable de operaciones con divisas, un arbitraje, en un ciclo negativo, que Bellman–Ford puede encontrar.
Pruébalo
Abre la aplicación y pulsa Paso. Cada arista es de un solo sentido, y algunas longitudes son negativas. Cada paso revisa una arista, en un orden fijo, y los paneles muestran la pasada y cuántas distancias ha cambiado. Normalmente pronto una pasada ya no cambia nada y la búsqueda para antes. Marca Añadir un ciclo negativo y mira cómo las distancias bajan pasada a pasada hasta que la pasada de comprobación encuentra el ciclo y lo dibuja en rojo.
Preguntas frecuentes
¿Cuál es la complejidad temporal de Bellman–Ford?
O(V · E) para V nodos y E aristas: hasta V − 1 pasadas, cada una revisando todas las aristas. Con la parada anticipada suele ser mucho más rápido en la práctica, y en el mejor caso basta una sola pasada.
¿Qué es un ciclo negativo?
Un ciclo cuyas longitudes de arista suman menos de cero. Recorrerlo una y otra vez hace un camino tan corto como se quiera, así que las distancias más cortas a todos los nodos alcanzables a través de él no están definidas.
¿Funciona Bellman–Ford en grafos no dirigidos?
Solo si ninguna arista es negativa: una arista negativa no dirigida se puede cruzar de ida y vuelta, y eso es un ciclo negativo de dos aristas. Con aristas no negativas funciona, pero el algoritmo de Dijkstra es más rápido.
¿Qué es SPFA?
El Shortest Path Faster Algorithm, una versión de Bellman–Ford que, con una cola, solo vuelve a revisar las aristas que salen de nodos cuya distancia acaba de cambiar. Suele ser mucho más rápido, aunque su peor caso es el mismo.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Prueba Bellman–Ford