Algorytm Bellmana–Forda

W niektórych problemach najkrótszej ścieżki są krawędzie, które czynią ścieżkę tańszą: zwrot pieniędzy, odcinek z górki, korzystny kurs wymiany. Algorytm Dijkstry sobie z nimi nie radzi. Algorytm Bellmana–Forda tak, bo zamiast sprytu stawia na cierpliwość.

Graf z jednokierunkowymi strzałkami, kilkoma ujemnymi krawędziami, dotychczasowymi odległościami na wierzchołkach i cyklem ujemnym narysowanym na czerwono
Graf z jednokierunkowymi strzałkami, kilkoma ujemnymi krawędziami, dotychczasowymi odległościami na wierzchołkach i cyklem ujemnym narysowanym na czerwono

Idea

Każdy algorytm najkrótszych ścieżek opiera się na jednym ruchu, relaksacji krawędzi: jeśli dojście do u, a potem krawędzią u → v jest krótsze niż najlepsza znana droga do v, użyj go. Algorytm Dijkstry relaksuje każdą krawędź raz, w sprytnej kolejności, która działa tylko wtedy, gdy żadna krawędź nie jest ujemna. Algorytm Bellmana–Forda niczego takiego nie zakłada. Relaksuje każdą krawędź, w dowolnej stałej kolejności, raz po raz, aż odległości przestaną się zmieniać.

Krok po kroku

Daj startowi odległość 0, a każdemu innemu wierzchołkowi nieskończoność. Powtórz n − 1 razy dla n wierzchołków: przejdź przez każdą krawędź u → v i zrelaksuj ją, jeśli u ma odległość. Zakończ wcześniej, jeśli cały przebieg niczego nie zmienia. Potem wykonaj jeszcze jeden przebieg. Jeśli jakąś krawędź wciąż da się zrelaksować, ze startu osiągalny jest cykl o ujemnej sumie; w przeciwnym razie każda odległość jest najkrótsza, a zapamiętane wierzchołki dają ścieżki.

Przykład

Weź jednokierunkowe krawędzie A → B o długości 4, A → C 5, B → D 2 i C → B −3, sprawdzane w tej kolejności, od A. Przebieg 1 daje B 4, C 5 i D 6, a potem C → B obniża B do 5 − 3 = 2. Przebieg 2 obniża D do 2 + 2 = 4. Przebieg 3 niczego nie zmienia, więc wynik to B 2, C 5, D 4. Algorytm Dijkstry uznałby B za ostateczne przy 4, a D przy 6, zanim zobaczyłby ujemną krawędź. Dodaj krawędź D → C o długości −4, a cykl C → B → D → C da sumę −5: każdy przebieg znowu obniża odległości, a przebieg kontrolny to zgłasza.

Dlaczego wystarcza n − 1 przebiegów

Najkrótsza ścieżka, jeśli istnieje, nigdy nie powtarza wierzchołka, więc ma co najwyżej n − 1 krawędzi. Relaksacja każdej krawędzi w przebiegu wydłuża każdą poprawnie znaną najkrótszą ścieżkę o jeszcze jedną krawędź, niezależnie od kolejności krawędzi. Zatem po przebiegu k wszystkie najkrótsze ścieżki o co najwyżej k krawędziach są poprawne, a po n − 1 przebiegach wszystkie. Kolejność wpływa jednak na szybkość: przy dobrej kolejności wystarczą jeden lub dwa przebiegi.

Historia i zastosowania

Alfonso Shimbel opisał tę metodę w 1955 roku, Lester Ford Jr. w 1956, Edward F. Moore w 1957, a Richard Bellman w 1958 roku; nosi nazwiska dwóch z nich, Bellmana i Forda. Jej przebiegi może wykonywać każdy router osobno, dlatego stała się podstawą protokołów routingu wektora odległości, takich jak RIP. W finansach ujemny logarytm kursów wymiany zamienia zyskowną serię wymian walut w cykl ujemny, który algorytm Bellmana–Forda potrafi znaleźć.

Richard Bellman w 1962 roku, fotografia Alfreda Eisenstaedta. Opublikował metodę najkrótszych ścieżek w 1958 roku, po Shimbelu, Fordzie i Moorze.
Richard Bellman w 1962 roku, fotografia Alfreda Eisenstaedta. Opublikował metodę najkrótszych ścieżek w 1958 roku, po Shimbelu, Fordzie i Moorze.

Wypróbuj

Otwórz aplikację i naciśnij Krok. Każda krawędź jest jednokierunkowa, a niektóre długości są ujemne. Każdy krok sprawdza jedną krawędź, w stałej kolejności, a kafelki pokazują przebieg i liczbę odległości, które zmienił. Zwykle przebieg szybko przestaje cokolwiek zmieniać i wyszukiwanie kończy się wcześniej. Zaznacz Dodaj cykl ujemny i patrz, jak odległości maleją przebieg po przebiegu, aż przebieg kontrolny znajdzie cykl i narysuje go na czerwono.

Często zadawane pytania

Jaka jest złożoność czasowa algorytmu Bellmana–Forda?

O(V · E) dla V wierzchołków i E krawędzi: do V − 1 przebiegów, z których każdy sprawdza każdą krawędź. Dzięki wczesnemu zatrzymaniu w praktyce często jest dużo szybszy, a w najlepszym przypadku wystarcza jeden przebieg.

Czym jest cykl ujemny?

Cyklem, którego długości krawędzi sumują się do mniej niż zera. Krążenie po nim raz za razem skraca ścieżkę dowolnie, więc najkrótsze odległości do wierzchołków osiągalnych przez ten cykl są nieokreślone.

Czy algorytm Bellmana–Forda działa na grafach nieskierowanych?

Tylko wtedy, gdy żadna krawędź nie jest ujemna: nieskierowaną ujemną krawędź można przechodzić tam i z powrotem, a to jest cykl ujemny z dwóch krawędzi. Przy nieujemnych krawędziach działa, ale algorytm Dijkstry jest szybszy.

Czym jest SPFA?

Shortest Path Faster Algorithm to wersja algorytmu Bellmana–Forda, która za pomocą kolejki ponownie sprawdza tylko krawędzie wychodzące z wierzchołków, których odległość właśnie się zmieniła. Często jest dużo szybsza, choć jej najgorszy przypadek jest taki sam.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Wypróbuj algorytm Bellmana–Forda