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ść.
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źć.
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