Bellman-Ford

Caminos más cortos con pesos de arista NEGATIVOS — el caso que Dijkstra no puede manejar. Relaja todas las aristas, V−1 veces.

Por qué Dijkstra se rompe

• Dijkstra cierra un nodo la primera vez que lo saca de la cola — congela su distancia
• Una arista negativa puede revelar una ruta más barata después → ya es tarde, ya se cerró
• Bellman-Ford nunca cierra nada: relaja TODAS las aristas, pasada tras pasada
• Después de la pasada k: toda distancia alcanzable en ≤ k aristas es final

Mira cómo se propagan las distancias

Números = estimaciones de distancia · arista roja = negativa (2→1, w=−3). El nodo 1 baja de 4 → 2 por la arista negativa; la pasada 2 lo propaga hacia adelante.

Qué estás comprando

30% de aristas negativas → Dijkstra se equivoca en silencio en ~5% de los nodos. Bellman-Ford: siempre correcto.

Detección de ciclos de regalo

• V−1 pasadas dejan todo final (el camino simple más corto tiene ≤ V−1 aristas)
• Una V-ésima pasada que todavía relaja ⇒ hay un CICLO NEGATIVO alcanzable
• Entonces no existe camino más corto — reporta el ciclo (eso es detección de arbitraje)
• O(V·E): el precio de no ser astuto con el orden

Para llevar

Dijkstra es más rápido pero solo válido en grafos no negativos — miente, no truena. Bellman-Ford = programación dinámica sobre grafos, el respaldo que dice la verdad. Sigue: todos los pares de golpe → Floyd-Warshall.