Bellman-Ford
Tema: Grafos · temarios: Syllabus OCI · Syllabus IOI
📍 Para profundizar: esta ficha amplía las clases de la Ruta de Aprendizaje. Puedes estudiarla cuando un problema requiera esta herramienta.
Qué problema resuelve
Queremos las distancias mínimas desde un origen en un grafo dirigido que puede tener pesos negativos. Una arista negativa puede representar un descuento; Dijkstra no garantiza el resultado en ese caso.
Relajar u → v de peso w significa comprobar si llegar a u y recorrer esa arista mejora la mejor distancia conocida de v: dist[v] = min(dist[v], dist[u] + w). Solo se puede partir de un vértice ya alcanzable.
La entrada es una lista de aristas Edge {u, v, w}, con vértices entre 0 y n-1, n >= 1 y origen válido. Para representar una arista no dirigida se agregan ambos sentidos. Una arista negativa no dirigida permite ir y volver con costo negativo: ese caso no tiene distancias mínimas finitas para los vértices afectados.
Por qué repetimos las relajaciones
Considera 0 → 1 de peso 4, 1 → 2 de peso −3 y 0 → 2 de peso 5. El mejor camino hasta 2 cuesta 1. Si procesamos primero 1 → 2, inicialmente no podemos aprovecharlo: todavía no conocemos cómo llegar a 1. Otra pasada lo corrige.
Tras p pasadas ya se han considerado todos los caminos de hasta p aristas, y quizá algunos más: la implementación actualiza el mismo arreglo y puede propagar varias mejoras durante una pasada. El orden de las aristas cambia cuándo llega una mejora, pero no el resultado final cuando existe.
Sin ciclos negativos alcanzables, existe un camino mínimo simple hasta cada vértice alcanzable: eliminar un ciclo de costo no negativo no empeora el camino. Un camino simple tiene a lo más n-1 aristas. Por eso bastan n-1 pasadas.
Si después todavía se puede relajar una arista alcanzable, existe un ciclo negativo alcanzable. Repetirlo permite bajar el costo sin límite. La función devuelve false; no interpretes entonces todo el arreglo como distancias mínimas finales. Un ciclo negativo en una componente inaccesible desde el origen no provoca ese resultado.
Una variante distinta: a lo más k aristas
No basta cambiar n-1 por k. Con las aristas 0 → 1 → 2, ambas de peso 1 y en ese orden, una sola pasada in situ alcanza el vértice 2, aunque haya usado dos aristas.
La variante distancias_con_limite lee del arreglo anterior y escribe en uno nuevo. Así, una mejora usa como máximo una arista adicional. Copiar primero el arreglo conserva las opciones que usan menos aristas:
| Máximo de aristas | Distancia a 0 | Distancia a 1 | Distancia a 2 |
|---|---|---|---|
| 0 | 0 | ∞ | ∞ |
| 1 | 0 | 1 | ∞ |
| 2 | 0 | 1 | 2 |
Esta variante admite ciclos negativos porque limita la cantidad de aristas recorridas; no intenta detectar distancias sin cota inferior. k=0 solo permite el recorrido vacío desde el origen. «Exactamente k aristas» sería otro contrato: no se copiarían las distancias anteriores al iniciar cada pasada.
Implementación recomendada (C++)
struct Edge { int u, v; long long w; };
// dist[s]=0. Devuelve false si hay un ciclo negativo alcanzable.
bool bellman_ford(int n, int s, const vector<Edge>& edges, vector<long long>& dist) {
const long long INF = 1e18;
dist.assign(n, INF); dist[s] = 0;
for (int i = 0; i < n - 1; i++)
for (auto& e : edges)
if (dist[e.u] < INF && dist[e.u] + e.w < dist[e.v])
dist[e.v] = dist[e.u] + e.w;
for (auto& e : edges) // una pasada extra: si aún relaja, hay ciclo neg.
if (dist[e.u] < INF && dist[e.u] + e.w < dist[e.v]) return false;
return true;
}
// Distancias mínimas usando A LO MÁS k aristas; k >= 0.
// Lee solo la pasada anterior: una pasada incorpora como máximo una arista.
vector<long long> distancias_con_limite(int n, int s, const vector<Edge>& edges, int k) {
const long long INF = 1000000000000000000LL;
vector<long long> anterior(n, INF);
anterior[s] = 0;
for (int paso = 0; paso < k; paso++) {
vector<long long> siguiente = anterior;
for (const auto& e : edges)
if (anterior[e.u] < INF)
siguiente[e.v] = min(siguiente[e.v], anterior[e.u] + e.w);
anterior.swap(siguiente);
}
return anterior;
}INF = 10^18 representa inaccesibilidad. Se supone que los pesos y todas las sumas intermedias realizadas quedan estrictamente entre -INF e INF; verifica esta condición con los límites del problema, especialmente si hay ciclos negativos. El centinela no impide por sí solo un desbordamiento.
Costo: Bellman-Ford usa O(n+n·m) tiempo y O(n) memoria adicional a la lista de m aristas. La variante limitada usa O(n+k·(n+m)) tiempo porque también copia n distancias en cada pasada, y O(n) memoria adicional.
Para practicar la distinción
Invierte el orden de las dos aristas del ejemplo de la tabla. Con una arista permitida, el vértice 2 debe seguir siendo inaccesible. Después agrega 1 → 1 de peso −2: la versión sin límite detecta un ciclo negativo; la versión limitada sigue teniendo una respuesta finita para cada k.