Algoritmo Bellman-Ford
Última actualización
Bellman-Ford encuentra el camino más corto desde un nodo origen hacia todos los demás nodos y, a diferencia de Dijkstra, funciona incluso cuando algunos pesos de arista son negativos. Funciona mediante relajación por fuerza bruta: recorre repetidamente cada arista y, si pasar por esa arista da una distancia menor, actualiza la distancia del nodo destino. Pulsa reproducir arriba para ver cómo bajan las distancias tentativas pasada a pasada.
Tras V - 1 pasadas sobre todas las aristas, se ha encontrado cada camino más corto (que puede tener como máximo V - 1 aristas). Esto lo hace O(V · E) - más lento que Dijkstra, pero maneja pesos negativos y puede detectar un ciclo de peso negativo (si una pasada V-ésima aún relaja una arista, no existe camino más corto).
Complejidad temporal y espacial
| Medida | Complejidad | Notas |
|---|---|---|
| Tiempo | O(V · E) | V − 1 pasadas sobre todas las E aristas |
| Espacio | O(V) | Una distancia por nodo |
| Pesos negativos | Compatible | Su ventaja clave frente a Dijkstra |
| Ciclos negativos | Detectables | Una V-ésima pasada que relaja indica uno |
Paso a paso
| Paso | Qué ocurre |
|---|---|
| 1 | Fija la distancia del origen en 0 y las demás en infinito. |
| 2 | Repite el siguiente paso V − 1 veces. |
| 3 | Para cada arista (u → v, w), comprueba si dist[u] + w < dist[v]. |
| 4 | Si es así, relájala: fija dist[v] = dist[u] + w. |
| 5 | Detente antes si una pasada completa no cambia nada. |
Ejemplo resuelto
Origen S sobre 4 nodos S, A, B, C con aristas S→A (4), S→B (5), A→C (3), B→A (-3), relajadas en ese orden. Las distancias empiezan en S=0 y todo lo demás en ∞:
| Pasada | Distancias [S, A, B, C] | Acción |
|---|---|---|
| Init | [0, ∞, ∞, ∞] | La distancia del origen es 0, todas las demás infinito. |
| 1 | [0, 2, 5, 7] | Relaja S→A a 4, S→B a 5, A→C a 7, y luego B→A baja A a 5 + (-3) = 2. |
| 2 | [0, 2, 5, 5] | A→C ahora mejora C a 2 + 3 = 5; ninguna otra arista se relaja. |
| 3 | [0, 2, 5, 5] | Ninguna arista se relaja, así que las distancias son definitivas: A cuesta 2 vía S→B→A. |
Cuándo usar Bellman-Ford
| Úsalo cuando | Evítalo cuando |
|---|---|
| Los pesos de arista pueden ser negativos. | Todos los pesos son no negativos (Dijkstra es más rápido). |
| Debes detectar ciclos de peso negativo. | El grafo es enorme y denso - O(V · E) es demasiado lento. |
| El grafo es pequeño o disperso. | Solo necesitas una consulta origen-destino en un grafo grande. |
| Necesitas una base sencilla y fácil de implementar. | Los pesos son no negativos y la latencia importa. |
Código de Bellman-Ford Algorithm
Una implementación limpia y ejecutable de Bellman-Ford Algorithm en Python, JavaScript, Java, C++, C. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código de Bellman-Ford Algorithm en Python
Python
1def bellman_ford(vertices, edges, start):2 dist = {v: float("inf") for v in vertices}3 dist[start] = 04 # Relax every edge V-1 times5 for _ in range(len(vertices) - 1):6 for u, v, w in edges:7 if dist[u] + w < dist[v]:8 dist[v] = dist[u] + w9 # One more pass: any improvement means a negative cycle10 for u, v, w in edges:11 if dist[u] + w < dist[v]:12 raise ValueError("Graph contains a negative-weight cycle")13 return dist14
15
16vertices = ["A", "B", "C", "D", "E"]17edges = [18 ("A", "B", 6), ("A", "C", 7), ("B", "D", 5), ("B", "E", -4),19 ("C", "D", -3), ("D", "B", -2), ("E", "D", 7),20]21
22for node, d in bellman_ford(vertices, edges, "A").items():23 print(f"A -> {node}: {d}")Código de Bellman-Ford Algorithm en JavaScript
JavaScript
1const nodes = ["A", "B", "C", "D", "E"];2const edges = [3 ["A", "B", 6], ["A", "C", 7], ["B", "D", 5], ["B", "E", -4],4 ["C", "D", -3], ["D", "B", -2], ["E", "A", 2],5];6
7function bellmanFord(source) {8 const dist = Object.fromEntries(nodes.map((n) => [n, Infinity]));9 dist[source] = 0;10 // Relax every edge V-1 times11 for (let i = 0; i < nodes.length - 1; i++) {12 for (const [u, v, w] of edges) {13 if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;14 }15 }16 // One more pass: any improvement means a negative cycle17 for (const [u, v, w] of edges) {18 if (dist[u] + w < dist[v]) throw new Error("Negative cycle detected");19 }20 return dist;21}22
23console.log("Shortest distances from A:", bellmanFord("A"));Código de Bellman-Ford Algorithm en Java
Java
1import java.util.Arrays;2
3public class Main {4 public static void main(String[] args) {5 int n = 5;6 // Directed edges {from, to, weight}; negative weights allowed7 int[][] edges = {8 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {1, 2, 8},9 {2, 4, 9}, {3, 1, -2}, {4, 3, 7}, {2, 3, -3}10 };11 int[] dist = new int[n];12 Arrays.fill(dist, Integer.MAX_VALUE);13 dist[0] = 0;14
15 // Relax every edge V-1 times16 for (int i = 0; i < n - 1; i++) {17 for (int[] e : edges) {18 if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {19 dist[e[1]] = dist[e[0]] + e[2];20 }21 }22 }23
24 // One more pass: any improvement means a negative cycle25 boolean hasNegativeCycle = false;26 for (int[] e : edges) {27 if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {28 hasNegativeCycle = true;29 }30 }31
32 System.out.println("Distances from 0: " + Arrays.toString(dist));33 System.out.println("Negative cycle: " + hasNegativeCycle);34 }35}Código de Bellman-Ford Algorithm en C++
C++
1#include <iostream>2#include <vector>3
4struct Edge {5 int from, to, weight;6};7
8int main() {9 const int INF = 1000000000;10 const int n = 5;11 std::vector<Edge> edges = {12 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {2, 3, -3},13 {1, 4, -4}, {3, 4, 9}, {2, 1, -2},14 };15 std::vector<int> dist(n, INF);16 dist[0] = 0;17 // Relax every edge V-1 times18 for (int pass = 0; pass < n - 1; ++pass) {19 for (const Edge& e : edges) {20 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {21 dist[e.to] = dist[e.from] + e.weight;22 }23 }24 }25 // One extra pass: any improvement means a negative cycle26 bool negativeCycle = false;27 for (const Edge& e : edges) {28 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {29 negativeCycle = true;30 }31 }32 if (negativeCycle) {33 std::cout << "Negative cycle detected\n";34 } else {35 for (int v = 0; v < n; ++v) {36 std::cout << "Distance 0 -> " << v << ": " << dist[v] << "\n";37 }38 }39 return 0;40}Código de Bellman-Ford Algorithm en C
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7typedef struct {8 int from, to, weight;9} Edge;10
11int main(void) {12 Edge edges[] = {13 {0, 1, 6}, {0, 2, 7}, {1, 3, 5}, {2, 3, -3},14 {1, 4, -4}, {3, 4, 9}, {2, 1, -2},15 };16 int m = sizeof(edges) / sizeof(edges[0]);17 int dist[N];18 for (int v = 0; v < N; v++) dist[v] = INF;19 dist[0] = 0;20 // Relax every edge V-1 times21 for (int pass = 0; pass < N - 1; pass++) {22 for (int i = 0; i < m; i++) {23 Edge e = edges[i];24 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {25 dist[e.to] = dist[e.from] + e.weight;26 }27 }28 }29 // One extra pass: any improvement means a negative cycle30 bool negativeCycle = false;31 for (int i = 0; i < m; i++) {32 Edge e = edges[i];33 if (dist[e.from] != INF && dist[e.from] + e.weight < dist[e.to]) {34 negativeCycle = true;35 }36 }37 if (negativeCycle) {38 printf("Negative cycle detected\n");39 } else {40 for (int v = 0; v < N; v++) {41 printf("Distance 0 -> %d: %d\n", v, dist[v]);42 }43 }44 return 0;45}Preguntas frecuentes sobre Bellman-Ford
¿Cuál es la complejidad temporal de Bellman-Ford?
Bellman-Ford se ejecuta en tiempo
O(V · E): hace V - 1 pasadas y cada pasada relaja las E aristas. Eso es más lento que el O((V + E) log V) de Dijkstra, que es el precio de admitir pesos de arista negativos.¿Cuándo debería usar Bellman-Ford en lugar de Dijkstra?
Usa Bellman-Ford cuando el grafo pueda tener pesos de arista negativos, o cuando necesites detectar ciclos de peso negativo. Dijkstra es más rápido pero solo es correcto con pesos no negativos. Un uso real común es la detección de arbitraje en cambio de divisas, donde importan los ciclos negativos.
¿Cómo detecta Bellman-Ford un ciclo negativo?
Tras las
V - 1 pasadas de relajación, todos los caminos más cortos quedan finalizados si no existe un ciclo negativo. Si una pasada más aún puede relajar una arista, entonces hay un ciclo de peso negativo alcanzable, y los caminos más cortos quedan indefinidos (podrías repetir el bucle eternamente para reducir el coste).¿Cuál es la diferencia entre Bellman-Ford y Floyd-Warshall?
Bellman-Ford calcula los caminos más cortos desde un único origen en
O(V · E), mientras que Floyd-Warshall calcula los caminos más cortos entre todos los pares en O(V³). En un grafo denso, ejecutar Bellman-Ford desde cada origen cuesta O(V² · E), así que Floyd-Warshall suele ser la mejor opción cuando necesitas todos los pares. Ambos manejan aristas negativas y pueden señalar ciclos negativos.¿Por qué Bellman-Ford necesita exactamente V - 1 pasadas?
Cualquier camino más corto en un grafo sin ciclos negativos usa como máximo
V - 1 aristas, porque un camino que visite más de V nodos debe repetir uno. Cada pasada garantiza que se relaja correctamente al menos una arista más de cada camino más corto, así que V - 1 pasadas bastan para fijarlos todos. Un error común es creer que más pasadas mejoran el resultado - nunca lo hacen, salvo que exista un ciclo negativo.¿Puede Bellman-Ford detenerse antes?
Sí. Si una pasada completa sobre todas las aristas no relaja nada, todas las distancias ya son óptimas y puedes detenerte antes de alcanzar las
V - 1 pasadas. Esta optimización de salida anticipada suele hacerlo mucho más rápido en grafos que convergen pronto, aunque la cota en el peor caso sigue siendo O(V · E).Recursos relacionados
Más visualizaciones
