Tema
Algoritmo de Bellman Ford
- Algoritmos
- Nivel intermedio
El algoritmo de Bellman Ford calcula caminos mínimos desde un origen admitiendo pesos negativos, y además detecta si existe un ciclo de peso negativo alcanzable.
Nombre en inglés
Bellman Ford algorithm
Intuición
La tabla se lee como programación dinámica sobre el número de aristas permitidas: La fila k guarda la mejor distancia que usa como mucho k aristas. Con V vértices, ningún camino simple necesita más de V menos 1 aristas, de modo que tras esas rondas la tabla se estabiliza. Si una ronda adicional todavía mejora algún valor, hay un ciclo negativo.
Fórmula
d_k[v] = min(d_{k-1}[v], min_u (d_{k-1}[u] + peso(u, v))) ; V - 1 rondas ; coste O(V E)
Ejemplo resuelto
Con vértices S, A y B y aristas de S a A de peso 4, de S a B de peso 5 y de B a A de peso -3, la primera ronda deja A en 4 y B en 5. La segunda ronda relaja A hasta 5 menos 3, es decir 2, mejor que el 4 anterior. Dijkstra habría fijado A en 4 durante el primer paso y nunca habría corregido ese valor.
Errores frecuentes
- Detener el algoritmo antes de V menos 1 rondas sin comprobar la estabilidad: Se puede parar antes si una ronda no cambia nada, y esa comprobación conviene programarla.
- Confundir arista negativa con ciclo negativo: Las aristas negativas son admisibles, mientras que un ciclo negativo hace que el camino mínimo deje de existir.
- Mezclar valores de la ronda actual con los de la anterior: Para leer la fila k como caminos de k aristas hay que relajar usando los valores de la ronda previa.
Ejercicio
Un grafo dirigido tiene 6 vértices. ¿Cuántas rondas de relajación ejecuta Bellman Ford antes de la comprobación de ciclo negativo?
Ver la solución
Un camino simple entre dos vértices usa como mucho V menos 1 aristas, y aquí V vale 6.
Respuesta: 5