Bellman-Ford: Najkrótsze Ścieżki Kiedy Niektóre Krawędzie Odejmować Zamiast Dodawać

Algorytm Dijkstry ma słaby punkt

Algorytm Dijkstry efektywnie znajduje najkrótsze ścieżki, ale zakłada, że każda waga krawędzi jest nieujemna – bezwzględnie finalizuje najbliższego niezakreszonego węzła jako pierwszego, zakładając, że późniejsze odkrycia nigdy nie skróciłyby już zakończonej ścieżki. Krawędź o ujemnej wadze narusza to założenie: ścieżka, która wydawała się dłuższa na pierwszy rzut oka, mogła nadal okazać się krótsza po uwzględnieniu krawędzi o ujemnej wadze później. Algorytm Bellmana-Forda, opracowany niezależnie przez Richarda Bellmana i Lestera Forda w latach 50., poprawnie obsługuje krawędzie o ujemnej wadze, rezygnując z żądnego skrótów podejścia Dijkstry i zamiast tego wielokrotnie rozwijając każdą krawędź w grafie.

Relaxation, repeated exactly V-1 times

Relaxing an edge (u, v) with weight w means: if the best known distance to u, plus w, is less than the best known distance to v, update v's distance to that better value. Bellman-Ford's entire algorithm is: initialise the source's distance to 0 and everything else to infinity, then relax every edge in the graph, and repeat that full pass V-1 times, where V is the number of vertices.

dist[source] = 0; dist[all others] = Infinity repeat (V - 1) times: for each edge (u, v, w) in the graph: if dist[u] + w < dist[v]: dist[v] = dist[u] + w // one more pass to check for negative cycles: for each edge (u, v, w): if dist[u] + w < dist[v]: report "negative cycle reachable from source" Why V-1 passes exactly? A shortest path between any two vertices, if one exists and the graph has no negative cycle, visits at most V-1 edges (a path visiting more than that would have to repeat a vertex, meaning it contains a cycle, and removing that cycle can only shorten the path in a graph with no negative cycles making it beneficial to keep). Each full pass over all edges is guaranteed to correctly extend at least one more shortest path by one additional edge, in the worst case propagating the correction one hop further down the longest possible shortest path per pass — so V-1 passes are sufficient to guarantee every shortest path, however many edges it needs, has been fully relaxed.

dist[source] = 0;  dist[all others] = Infinity
repeat (V - 1) times:
  for each edge (u, v, w) in the graph:
    if dist[u] + w < dist[v]:
      dist[v] = dist[u] + w
// one more pass to check for negative cycles:
for each edge (u, v, w):
  if dist[u] + w < dist[v]:  report "negative cycle reachable from source"

Dodatek: Wykrywanie cykli ujemnych bez dodatkowych kosztów

Jeśli z punktu początkowego można dotrzeć do cyklu o ujemnym ciężarze, najkrótsze ścieżki przez niego są w zasadzie nieokreślone – można nieskończenie wiele razy iterować po tym cyklu, a każda taka pętla jeszcze bardziej zmniejsza całkowity koszt ścieżki, tak że prawdziwa najkrótsza ścieżka wynosi ujemność nieskończoności. Algorytm Bellmana-Ford wykrywa to bez problemu, wykonując dodatkowy przebieg relaksacji po głównym V-1; jeśli w tym dodatkowym przebiegu można jeszcze jakąkolwiek krawędź zrelaksować, oznacza to, że szacowana najkrótsza ścieżka nie uległa konwergencji, co jest możliwe tylko wtedy, gdy cykl o ujemnym ciężarze, osiągalny z punktu początkowego, ją zniekształca. Ta zdolność wykrywania, a nie tylko tolerancja na krawędzie o ujemnym ciężarze, to główny powód, dla którego algorytm Bellmana-Ford pozostaje standardem, mimo że jest wolniejszy niż Dijkstra.

Koszt ogólności: O(V·E) zamiast O(E log V)

Algorytm Dijkstry z kopcem binarne lub Fibonacciego działa w przybliżeniu w czasie O(E log V) lub lepszym; algorytm Bellmana-Forda, który wykonuje V-1 przejść po wszystkich E krawędziach, kosztuje O(V*E), co jest znacznie wolniejsze na dużych, gęstych grafach. W praktyce ta kompromis jest zwykle opłacalna tylko wtedy, gdy potrzebne jest reprezentowanie wag ujemnych, lub gdy istotne są inne właściwości algorytmu Bellmana-Forda: ponieważ jest to prosty, jednolity cykl z relaksacją każdej krawędzi bez stosu priorytetów, łatwiej się go równolegle i rozdziela niż sekwencyjny, głodowy wybór algorytmu Dijkstry, co dokładnie wyjaśnia, dlaczego protokoły routingu wektorów odległości, takie jak oryginalny RIP, wykorzystują rozproszoną wersję Bellmana-Forda, w której każdy router musi znać jedynie szacowane odległości swoich bezpośrednich sąsiadów, a nie całą topologię sieci.

Skąd biorą się ujemne wagi w praktyce

Ujemne wagi krawędzi nie są jedynie ciekawostką z podręczników: pojawiają się, gdy krawędź reprezentuje netto zysk, a nie czystą stratę. Dotyczy to analizy arbitrażu w grafach wymiany walut, gdzie logarytm kursu wymiany może być ujemny, oraz cykli negatywnych, które dosłownie opisują dochodową pętlę arbitrażową. W przypadku problemów z planowaniem, gdzie krawędź może kodować wymagany odstęp czasowy, który może być ujemny, algorytm Bellmana-Forda do wykrywania cykli negatywnych nie jest przypadkowym problemem do obrony – to rzeczywista odpowiedź, której algorytm ma znaleźć.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Bellman-Ford i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.