Algorytm Bellmana-Forda
- Autor metody
- Richard Bellman and Lester R. Ford
- Rok
- 1956
- Typ
- algorithm
- Rodzina
- Graph Algorithms
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Algorytm Bellmana-Forda, opracowany przez Richarda Bellmana i Lestera R. Forda w latach 50.
XX wieku, jest fundamentalnym algorytmem do obliczania najkrótszych ścieżek w grafach ważonych, które mogą zawierać krawędzie o ujemnych wagach. W przeciwieństwie do algorytmu Dijkstry, poprawnie obsługuje ujemne wagi i potrafi wykryć obecność cykli o ujemnych wagach.
Intuicja stojąca za metodą
Algorytm działa poprzez iteracyjne rozluźnianie krawędzi: dla każdej krawędzi sprawdza, czy przejście przez tę krawędź oferuje krótszą ścieżkę do celu niż obecna najlepsza znana ścieżka. Powtarzając ten proces dla wszystkich krawędzi V-1 razy, gdzie V to liczba wierzchołków, algorytm gwarantuje znalezienie najkrótszej ścieżki nawet przy ujemnych wagach. Kluczowe spostrzeżenie polega na tym, że każda najkrótsza ścieżka w grafie z V wierzchołkami zawiera co najwyżej V-1 krawędzi; jeśli odległości nadal się poprawiają po V-1 iteracjach, musi istnieć ujemny cykl.
Historia
Richard Bellman opracował algorytm w 1958 roku, wykorzystując zasady programowania dynamicznego, podczas gdy Lester R. Ford niezależnie odkrył podobne podejście do przepływów sieciowych w 1956 roku. Algorytm był dalej rozwijany i udoskonalany w latach 60. XX wieku, a jego zastosowania rozszerzyły się na trasowanie sieci i zastosowania ekonomiczne. Nowoczesne warianty obejmują algorytm Shortest Path Faster Algorithm (SPFA) i różne optymalizacje dla specyficznych struktur grafów, chociaż podstawowe podejście Bellmana-Forda pozostaje klasycznym punktem odniesienia w projektowaniu algorytmów.
Kiedy stosować
Zastosuj algorytm Bellmana-Forda przy obliczaniu najkrótszych ścieżek w grafach z ujemnymi wagami krawędzi. Jest on niezbędny do wykrywania arbitrażu walutowego, protokołów sieciowych, gdzie wagi mogą być ujemne, oraz wszelkich zastosowań, gdzie ujemne koszty lub wagi mają znaczenie. Użyj algorytmu Dijkstry, jeśli wszystkie wagi są nieujemne, ponieważ jest on bardziej wydajny. Do wykrywania ujemnych cykli bez obliczania ścieżek ten algorytm jest również odpowiedni.
Ograniczenia i uwagi
- Wolniejszy niż Dijkstra dla wag nieujemnych: O(VE) w porównaniu do O((V+E)logV)
- Mniej wydajny dla rzadkich grafów w porównaniu do innych algorytmów
- Wymaga jawnego wymienienia wszystkich krawędzi, co czyni go mniej odpowiednim dla grafów niejawnych lub dynamicznych
- Brak dostępnego wsparcia heurystycznego w celu przyspieszenia obliczeń
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Poprawnie obsługuje grafy z ujemnymi wagami krawędzi
- Wykrywa cykle o ujemnych wagach, zapobiegając błędnym wynikom najkrótszych ścieżek
- Prostszy do zrozumienia i zaimplementowania niż niektóre zaawansowane algorytmy najkrótszych ścieżek
- Gwarantuje znalezienie najkrótszych ścieżek w czasie O(VE)
- Działa zarówno na grafach skierowanych, jak i nieskierowanych (z ostrożnością na nieskierowanych)
Zastosowania
- Wykrywanie arbitrażu walutowego: identyfikacja zyskownych cykli w grafach kursów wymiany walut
- Protokoły routingu sieciowego: obliczanie najkrótszych ścieżek, gdzie koszty połączeń mogą się zmieniać lub być ujemne
- Teoria gier: rozwiązywanie problemów najkrótszych ścieżek z krawędziami kary lub czynnikami dyskontującymi
- Robotyka: planowanie ścieżek w środowiskach z siłami odpychającymi (ujemne wagi)
- Optymalizacja dyspozycji (Economic dispatch): optymalizacja generacji mocy z funkcjami kosztów zawierającymi ujemne terminy
- Telekomunikacja: znajdowanie optymalnych tras, gdy wagi połączeń reprezentują metryki opóźnienia lub jakości
Jak to działa
Jak to działa
Ustaw odległość do źródła na zero, a wszystkie inne odległości na nieskończoność; opcjonalnie ustaw wszystkich poprzedników na null.
Powtórz V-1 razy: dla każdej krawędzi (u, v) o wadze w, jeśli odległość[u] + w jest mniejsza niż odległość[v], zaktualizuj odległość[v] i poprzednika v.
Sprawdź wszystkie krawędzie jeszcze raz; jeśli jakakolwiek odległość się poprawi, istnieje cykl o ujemnej wadze. Zwróć błąd lub zidentyfikuj cykl odpowiednio.
Częste pułapki
- Zapomnienie o wykonaniu dodatkowej iteracji w celu wykrycia ujemnych cykli
- Zakładanie, że algorytm działa poprawnie na grafach nieskierowanych z ujemnymi krawędziami (może tworzyć wirtualne ujemne cykle)
- Używanie algorytmu, gdy Dijkstra jest wystarczający, co prowadzi do niepotrzebnej utraty wydajności
Najczęściej zadawane pytania
Dlaczego algorytm potrzebuje dokładnie V-1 iteracji?
Każda ścieżka w grafie z V wierzchołkami ma co najwyżej V-1 krawędzi. Poprzez V-1 iteracji algorytm pozwala informacjom o odległościach propagować się przez cały graf. V-ta iteracja poprawi odległości tylko wtedy, gdy istnieje ujemny cykl.
Jak algorytm może wykryć ujemne cykle?
Po zakończeniu V-1 iteracji wykonaj jeszcze jedną rundę rozluźniania. Jeśli jakakolwiek odległość się zmniejszy, istnieje ujemny cykl. Wierzchołki zaangażowane w cykl można zidentyfikować poprzez cofanie się za pomocą wskaźników poprzedników.
Jaka jest złożoność czasowa i jak porównuje się z Dijkstrą?
Algorytm Bellmana-Forda działa w czasie O(VE), gdzie V to liczba wierzchołków, a E to liczba krawędzi. Dijkstra działa w czasie O((V+E)logV) z kopcem binarnym. Algorytm Bellmana-Forda jest wolniejszy, ale obsługuje ujemne wagi; Dijkstra jest szybszy, ale wymaga wag nieujemnych.
Czy algorytm Bellmana-Forda może działać na grafach nieskierowanych z ujemnymi wagami?
Technicznie tak, ale może tworzyć pozorne ujemne cykle ze względu na dwukierunkową naturę krawędzi. Wymagana jest szczególna ostrożność przy interpretacji wyników. W przypadku grafów nieskierowanych należy rozważyć alternatywne podejścia.
Pokrewne metody
Źródła
Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90.
Otwórz odnośnik DOISkopiowano.Ford, L. R. (1956). Network Flow Theory. RAND Corporation Paper P-923.
Otwórz odnośnik do publikacjiSkopiowano.