Motivazione

Bellman-Ford si basa su un’unica operazione, il rilassamento: per un arco u -> v di peso w, se passare per u è meno costoso (dist[u] + w < dist[v]), aggiorna dist[v]. Fallo per ogni arco, ripetutamente.

Perché imparare Bellman-Ford?

• Pesi negativi: funziona dove Dijkstra non può, ad esempio con costi che possono essere sconti o arbitraggio valutario.
• Rilevamento dei cicli negativi: un passaggio di rilassamento aggiuntivo rivela i cicli il cui peso totale è negativo.
• Semplicità: niente coda con priorità, solo rilassamenti ripetuti degli archi.

Il compromesso è la velocità: O(V * E), più lento di O((V + E) log V) di Dijkstra.