Bellman-Ford calcula caminos mínimos desde un origen incluso cuando existen pesos negativos. Además puede detectar ciclos negativos alcanzables que impiden definir ciertas distancias mínimas.
Dijkstra es eficiente, pero su estrategia voraz deja de ser segura cuando una arista tiene peso negativo. Bellman-Ford elimina esa restricción mediante una idea diferente: relajar sistemáticamente todas las aristas varias veces.
El algoritmo obtiene las distancias mínimas desde un origen, reconstruye rutas mediante predecesores y reconoce ciclos negativos que sean alcanzables desde ese origen.
Bellman-Ford es apropiado cuando:
Si todos los pesos son no negativos, Dijkstra suele ser más rápido.
Como en otros algoritmos de caminos mínimos, se comienza con:
El infinito significa que todavía no se conoce ningún camino desde el origen hasta ese vértice.
Para cada arista u → v de peso w se evalúa:
La comprobación de infinito evita realizar operaciones desde un vértice que todavía no es alcanzable.
Un camino mínimo simple en un grafo con V vértices utiliza como máximo V − 1 aristas. Si repitiera un vértice contendría un ciclo; cuando no hay ciclos negativos relevantes, ese ciclo puede eliminarse sin empeorar el camino.
Después de la ronda i, Bellman-Ford garantiza las mejores distancias para caminos de hasta i aristas, independientemente del orden en que estén almacenadas.
Avanza arista por arista para observar las relajaciones. Puedes activar D → A con peso −4; junto con A → C y C → D forma un ciclo de costo negativo.
Distancias y padres
Acción actual
Rosa señala la arista examinada y el vértice cuya distancia acaba de mejorar. Las aristas celestes representan los predecesores actuales.
Después de las V − 1 rondas se examinan nuevamente todas las aristas. Si alguna distancia todavía puede disminuir, existe un ciclo negativo alcanzable desde el origen.
La palabra alcanzable es importante: un ciclo negativo en una componente a la que el origen no puede llegar no afecta sus caminos mínimos.
function bellmanFord(vertices, aristas, origen) {
const distancia = Object.fromEntries(vertices.map(v => [v, Infinity]));
const padre = Object.fromEntries(vertices.map(v => [v, null]));
distancia[origen] = 0;
for (let ronda = 1; ronda < vertices.length; ronda++) {
let cambio = false;
for (const { origen: u, destino: v, peso } of aristas) {
if (distancia[u] !== Infinity &&
distancia[u] + peso < distancia[v]) {
distancia[v] = distancia[u] + peso;
padre[v] = u;
cambio = true;
}
}
if (!cambio) break;
}
for (const { origen: u, destino: v, peso } of aristas) {
if (distancia[u] !== Infinity &&
distancia[u] + peso < distancia[v]) {
return { distancia, padre, cicloNegativo: true };
}
}
return { distancia, padre, cicloNegativo: false };
}Si una ronda completa no produce ninguna mejora, las distancias ya son estables. Las rondas restantes no podrían cambiar nada y el algoritmo puede detenerse.
Esta optimización mejora muchos casos prácticos, aunque la complejidad del peor caso continúa siendo O(VE).
El resultado final no depende del orden de las aristas, pero la velocidad con la que se propagan las mejoras sí. Una ronda puede transmitir varias actualizaciones si las aristas aparecen en un orden favorable.
La garantía de V − 1 rondas cubre cualquier orden posible. Por eso no debemos asumir que una sola pasada basta solo porque funcionó en un ejemplo particular.
Cuando una relajación mejora a v, se guarda u como su padre. Si el destino tiene una distancia mínima finita y no está afectado por un ciclo negativo, la ruta se reconstruye siguiendo padres hacia el origen.
function reconstruir(padre, origen, destino) {
const camino = [];
let actual = destino;
while (actual !== null) {
camino.push(actual);
if (actual === origen) return camino.reverse();
actual = padre[actual];
}
return null;
}Si una relajación adicional mejora al vértice x, podemos seguir su cadena de padres V veces para asegurar que ingresamos al ciclo. Desde allí continuamos hasta repetir un vértice.
Mostrar el ciclo resulta útil para diagnosticar reglas de conversión, dependencias o transacciones inconsistentes.
No todos los vértices del grafo tienen necesariamente distancia −∞. Quedan afectados los nodos que pertenecen a un ciclo negativo alcanzable o que pueden alcanzarse desde él.
Después de detectar los vértices mejorables en la ronda adicional, una búsqueda desde ellos permite marcar todos los destinos afectados.
| Característica | Bellman-Ford | Dijkstra |
|---|---|---|
| Pesos negativos | Permitidos | No permitidos |
| Ciclos negativos | Los detecta | No los maneja |
| Estrategia | Relajar todas las aristas por rondas | Fijar el mínimo pendiente |
| Complejidad habitual | O(VE) | O((V + E) log V) |
Se realizan como máximo V − 1 rondas principales y cada una examina E aristas:
La ronda de detección agrega O(E), que no modifica la complejidad asintótica.
Bellman-Ford sacrifica velocidad para trabajar en un escenario más general que Dijkstra. Sus rondas garantizan la propagación de mejoras y su verificación final distingue los caminos mínimos válidos de situaciones dominadas por ciclos negativos.
En el próximo tema estudiaremos Floyd-Warshall, que calcula caminos mínimos entre todos los pares de vértices mediante programación dinámica.