Motywacja

Algorytm Bellmana-Forda opiera się na jednej operacji, relaksacji: dla krawędzi u -> v o wadze w, jeśli przejście przez u jest tańsze (dist[u] + w < dist[v]), zaktualizuj dist[v]. Powtarzaj to dla każdej krawędzi.

Dlaczego warto poznać algorytm Bellmana-Forda?

• Ujemne wagi: działa tam, gdzie Dijkstra sobie nie radzi, na przykład przy kosztach, które mogą uwzględniać rabaty, lub przy arbitrażu walutowym.
• Wykrywanie cykli o ujemnej wadze: jeden dodatkowy przebieg relaksacji ujawnia cykle, których łączna waga jest ujemna.
• Prostota: bez kolejki priorytetowej, tylko wielokrotna relaksacja krawędzi.

Kompromisem jest szybkość: O(V * E), wolniej niż O((V + E) log V) w algorytmie Dijkstry.