Wspomniany na wcześniejszym wykładzie algorytm Dijkstry pozwala na wyznaczenie najkrótszych ścieżek od startowego wierzchołka do wszystkich innych wierzchołków w grafie , w przypadku gdzie wagi krawędzi są dodatnie (). Teraz będziemy rozważać grafy, gdzie mamy również ujemne wagi krawędzi ().
W algorytmie Dijkstry wykorzystywany był następujący fakt:
najkrótsza ścieżka od wierzchołka startowego do wierzchołka może przechodzić tylko przez wierzchołki będące w mniejszej odległości od nie wierzchołek .
Własność ta nie jest prawdziwa jeśli dopuścimy ujemne wagi krawędzi grafu:
Zauważmy, że algorytm Dijkstry wykonuje pewną sekwencję procedur update
:
Procedura update
ma następujące własności:
update
może zostać wykonana nadmiarową liczbę razy.Widzimy zatem, że wykonując dowolną sekwencję procedur update
wartości dla każdego wierzchołka przyjmuje wartość większą lub równą prawdziwej najkrótszej odległości od wierzchołka startowego .
Na poprzedniej ilustracji widzieliśmy przykład grafu, dla którego sekwencja wykonań procedur update
wykonywana przez algorytm Dijkstry nie pozwoli wyznaczyć prawidłowej najkrótszej ścieżki od wierzchołka do . Zastanówmy się jakie własności musi mieć najkrótsza ścieżka od wierzchołka do (powiedzmy, że będzie ona wyglądać następująco ) oraz sekwencja procedur update
pozwalająca ją wyznaczyć:
update
zostanie wykonana na krawędziach w tej kolejności, to z pierwszej własności procedury update
wiemy, że odległość od do zostanie poprawnie wyliczona (bez względu na to dla jakich innych krawędzi grafu zostanie wykonana procedura update
)W celu uniknięcia zastanawiania się czy wykonamy procedurę update
w odpowiedniej kolejności możemy wykonać ją dla każdej krawędzi w grafie razy. Zauważmy jednak, że w przypadku wielu grafów ścieżki będą miały mnie krawędzi niż , czyli mniejsza liczba (niż ) powtórzeń procedury update
dla każdego wierzchołka wystarczy aby wyznaczyć najkrótsze ścieżki. Zauważmy, że jeśli wykonamy procedurę update
dla każdej krawędzi w grafie, ale nie zmodyfikujemy żadnej ścieżki to dalsze wykonywanie procedury update
już nic nie zmieni.
Bellman-Ford
:
for all
:
null
repeat until
:
for all
:
if
Złożoność obliczeniowa: wewnętrzna pętla ma złożoność obliczeniową i jest wykonywana co najwyżej razy co daje złożoność obliczeniową całego algorytmu .
Zauważmy, że jeśli w grafie istnieje ujemny cykl (tzn. suma wag krawędzi w cyklu jest ujemna) to przechodzenie w kolejne razy tego ujemnego cyklu będzie zmniejszać długość ścieżek w grafie. W takim przypadku zakładamy, że najkrótsza ścieżka nie istnieje. Aby sprawdzić, czy graf posiada ujemny cykl wystarczy powtórzyć wykonanie procedury update
dla każdej krawędzi razy. Jeśli w ostatniej rundzie wykonywania procedury update
któraś wartość ulegnie zmianie to wiemy, że w grafie mamy ujemny cykl (ponieważ jak wcześniej zauważyliśmy najkrótsza ścieżka może mieć co najwyżej krawędzi).