Motivation
Lección 2 de 9 del curso Algoritmo de Bellman-Ford - Algoritmos de grafos de Coddy.
Bellman-Ford se basa en una operación, relajación: para una arista u -> v de peso w, si pasar por u es más barato (dist[u] + w < dist[v]), actualiza dist[v]. Haz eso para cada arista, repetidamente.
¿Por qué aprender Bellman-Ford?
- Pesos negativos: funciona donde Dijkstra no puede, por ejemplo, costos que pueden ser reembolsos o arbitraje de divisas.
- Detección de ciclos negativos: una pasada de relajación adicional revela ciclos cuyo peso total es negativo.
- Simplicidad: sin cola de prioridad, solo relajación de aristas repetida.
La contrapartida es la velocidad: O(V * E), más lento que el O((V + E) log V) de Dijkstra.
Pruébalo tú mismo
Esta lección no incluye un desafío de código.
Ponte a pruebaEsta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.
