El algoritmo de Bellman-Ford encuentra la distancia más corta desde un único nodo de origen hasta cualquier otro nodo en un grafo dirigido ponderado, y funciona incluso cuando algunos pesos de las aristas son negativos.

Relajación de una arista

Cada arista (u, v) con peso w se relaja repetidamente según la regla dist[v] = min(dist[v], dist[u] + w(u, v)). Si el camino a través de u es más corto que la mejor distancia conocida hasta v, esa distancia — y el predecesor de v — se actualizan.

Por qué bastan V−1 pasadas

El camino más corto que no repite nodos recorre como máximo V−1 aristas. Cada pasada completa por todas las aristas garantiza que al menos una arista más de cada camino más corto quede finalizada, de modo que tras V−1 pasadas todos los caminos más cortos (en ausencia de un ciclo negativo) se han propagado por completo.

La pasada adicional V

Ejecutar una pasada más tras las obligatorias V−1 comprueba si existen ciclos negativos: si alguna distancia todavía puede mejorar, existe un ciclo de peso negativo alcanzable desde el origen, y para sus nodos el camino más corto no está bien definido.

Complejidad

Bellman-Ford se ejecuta en O(V·E) tiempo y O(V) espacio. Esto es más lento que el algoritmo de Dijkstra (O((V+E) log V)), pero, a diferencia de este, Bellman-Ford tolera pesos negativos y puede detectar ciclos negativos — la elección voraz de Dijkstra deja de funcionar correctamente en cuanto aparece una arista negativa.