Bellman-Ford i ujemne krawędzie

Dijkstra zakłada, że pobrana odległość jest ostateczna, ale ujemna krawędź może później obniżyć koszt ścieżki. Dlatego algorytm zawodzi.

Bellman-Ford obsługuje ujemne wagi krawędzi. Jest wolniejszy od algorytmu Dijkstry, ale sprawdza się tam, gdzie nie można ufać logice zachłannej.

Algorytm wielokrotnie wykonuje relaksację każdej krawędzi: jeśli dist[u] plus waga krawędzi daje wartość mniejszą niż dist[v], aktualizuje dist[v] tą mniejszą wartością.

Najkrótsza ścieżka używa najwyżej V minus 1 krawędzi, więc V-1 rund relaksacji wszystkich krawędzi wystarcza do ustalenia wszystkich odległości.

Na początku każdą odległość należy ustawić na nieskończoność, z wyjątkiem źródła, dla którego należy ustawić zero, dokładnie tak jak w algorytmie Dijkstry.

W każdym przejściu przechodzi się raz przez całą listę krawędzi i wykonuje relaksację każdej z nich. Ulepszenia rozchodzą się na zewnątrz o jeden krok w każdym przejściu.

Po k przejściach poprawne są wszystkie najkrótsze ścieżki używające k krawędzi. Po V-1 przejściach zakończona jest każda najkrótsza ścieżka prosta.

Należy wykonać jeszcze jedno przejście. Jeśli dowolna odległość nadal się zmniejsza, oznacza to, że można ją wciąż obniżać, co sygnalizuje ujemny cykl.

Ujemny cykl oznacza, że nie istnieje skończona najkrótsza ścieżka, ponieważ można wykonywać go w nieskończoność i bez ograniczeń obniżać koszt.

Relaksuje się E krawędzi w ciągu V przejść, więc algorytm Bellmana-Forda działa w czasie O(V * E), co wystarcza dla małych i średnich grafów.

Algorytm Dijkstra należy wybrać dla nieujemnych wag i wysokiej wydajności. Algorytm Bellmana-Forda należy wybrać, gdy występują wartości ujemne lub trzeba wykryć niepoprawny cykl.

Po V-1 przejściach odległość nadal zmniejsza się podczas kolejnego przejścia. Co to oznacza?

Należy relaksować wszystkie krawędzie przez V-1 przejść, a następnie wykonać jeszcze jedno, aby wykryć ujemne cykle. Algorytm działa w czasie O(V*E), ale sprawdza się tam, gdzie Dijkstra nie może być użyty. ✅