Bellman-Ford resuelve el problema de camino más corto desde una sola fuente en grafos con pesos de arista negativos, algo que Dijkstra no puede hacer. Relaja todas las aristas V-1 veces, garantizando distancias óptimas.

Su ventaja única: detecta ciclos de peso negativo (indicando que no hay camino más corto bien definido). Su costo: O(VE) — más lento que Dijkstra, pero necesario cuando hay pesos negativos.

Cómo Funciona

1. Inicializa: dist[source] = 0, todos los demás ∞.
2. Relaja todas las aristas V-1 veces (itera sobre la lista de aristas completa).
3. Detecta ciclos: en la iteración V, si alguna distancia se actualiza, hay un ciclo negativo alcanzable desde la fuente.

Idea Clave

¿Por qué V-1 iteraciones? En un grafo sin ciclos, el camino más simple entre dos nodos tiene a lo sumo V-1 aristas. Cada iteración de Bellman-Ford encuentra caminos que usan una arista más que la iteración anterior.

Después de V-1 iteraciones, todos los caminos simples más cortos han sido considerados. Si en la iteración V aún se actualiza alguna distancia, existe un ciclo negativo que puede reducir la distancia indefinidamente.

Ejemplo Trabajado

Grafo con posible ciclo negativo:

S → A (4)
S → B (5)
A → B (-3)  ← arista negativa
B → C (3)
C → A (-2)

Inicialización: dist = [S=0, A=∞, B=∞, C=∞]

Iteración 1 (relaja todas las aristas):

• “S→A: dist[A] = min(∞, 0+4) = 4”
• “S→B: dist[B] = min(∞, 0+5) = 5”
• “A→B: dist[B] = min(5, 4-3) = 1 ← mejorado”
• “B→C: dist[C] = min(∞, 1+3) = 4”
• “C→A: dist[A] = min(4, 4-2) = 2 ← mejorado”

Iteración 2:

• “S→A: no mejora”
• “S→B: no mejora”
• “A→B: dist[B] = min(1, 2-3) = -1 ← mejorado”
• “B→C: dist[C] = min(4, -1+3) = 2 ← mejorado”
• “C→A: dist[A] = min(2, 2-2) = 0 ← mejorado”

Iteración 3 (V-1 = 3):

• “Continúa mejorando: distancias siguen decreciendo”

Iteración 4 (V = 4):

• Si alguna distancia mejora → ciclo negativo detectado

Observa el visualizador mostrar las relajaciones y la detección de ciclos.

Casos Extremos y Trampas

• Ciclos negativos — Bellman-Ford los detecta; Dijkstra retorna resultados incorrectos silenciosamente.
• Grafo disperso — O(VE) puede ser lento para grafos grandes. Usa Dijkstra con cola de prioridad si no hay pesos negativos.
• Grafo no conexo — nodos inalcanzables mantienen dist = ∞.
• Múltiples ciclos negativos — Bellman-Ford reporta al menos uno; no distingue entre ellos.

Comparación con Dijkstra

Aplicaciones

• Redes con costos variables — enrutamiento con fluctuación de precios
• Detección de arbitraje — ciclos de ganancia en mercados financieros
• Grafos con descuentos — costos negativos representan rebajas
• Enseñanza — introduce relajación y sus límites

Trayectoria de Práctica

1. Ejecuta Bellman-Ford en el grafo del visualizador; registra dist después de cada iteración.
2. Construye un grafo con un ciclo negativo y muestra dónde se detecta en la iteración V.
3. Compara con Dijkstra en un grafo sin pesos negativos: ¿por qué Bellman-Ford es más lento?
4. Explica por qué V-1 iteraciones son suficientes para caminos simples.
5. Investiga el algoritmo de Floyd-Warshall: ¿cuándo es mejor para all-pairs?