Motivation

Bellman-Ford é construído sobre uma operação, relaxamento: para uma aresta u -> v de peso w, se passar por u for mais barato (dist[u] + w < dist[v]), atualize dist[v]. Faça isso para cada aresta, repetidamente.

Por que aprender Bellman-Ford?

• Pesos negativos: funciona onde Dijkstra não consegue, por exemplo, custos que podem ser descontos ou arbitragem de moedas.
• Detecção de ciclos negativos: uma passagem extra de relaxamento revela ciclos cujo peso total é negativo.
• Simplicidade: sem fila de prioridade, apenas relaxamento de arestas repetido.

A compensação é a velocidade: O(V * E), mais lento que o O((V + E) log V) de Dijkstra.