Algorytm Bellmana-Forda

03.10.2010 - Damian Rusak
TrudnośćTrudność

Zarys algorytmu

Odkryliśmy więc dwie zasadnicze różnice pomiędzy poszukiwaniem najkrótszej ścieżki w grafie, w którym krawędzie mają tylko nieujemne koszty i poszukiwaniem najkrótszej ścieżki w grafie, gdzie krawędzie mogą mieć wagi ujemne.

Zauważmy, że te dwie rzeczy pozwalają nam już określić w przybliżeniu, co powinien robić algorytm wyznaczony do tego zadania:

1. Jeśli w grafie istnieje ścieżka prowadząca od startu do celu przez jakiś ujemny cykl, należy to odkryć. Wtedy algorytm powinien udzielić odpowiedzi: nie ma najtańszej ścieżki, istnieje ścieżka dowolnie "tania".

2. Jeśli taka sytuacja nie występuje, to należy znaleźć najtańszą ścieżkę, pamiętając, że nie można posłużyć się rozwiązaniem dla grafów z krawędziami o wyłącznie nieujemnych kosztach.

Czy na poniższej ilustracji można doszukać się ujemnego cyklu? Chcemy dotrzeć z wierzchołka H do A. Zauważ, że problem jest interesujący, gdyż ujemny cykl może mieć dużo krawędzi o dodatnich wagach, równoważonych przez krawędzie ujemne. Wystarczy wszak, żeby waga cyklu wynosiła nie więcej niż -1.

Ale znaleźć ujemne cykle nie jest prosto. Zauważ jednak, że nas nie interesuje znalezienie jakiegoś konkretnego ujemnego cyklu do którego można dojść. Nas interesuje to, czy jakikolwiek taki istnieje. Zamiast więc poszukiwać ujemnych cykli, odwrócimy trochę kolejność tych punktów. Algorytm, który poznamy, zadziała w ten sposób:

1. Szukajmy poprawnie najkrótszej ścieżki tak, jakby nie było problemu z ujemnymi cyklami. 

2. Sprawdźmy, czy problem z ujemnym cyklem wystąpił. W jaki sposób? Szybko skontrolujmy, czy rozwiązania z punktu pierwszego nie da się poprawić. Jeśli się da (a przecież szukaliśmy poprawnie), to znaczy, że można znaleźć ścieżkę z ujemnym cyklem.

I to wszystko, co potrzebujemy wiedzieć.

Aby zgromadzić arsenał odpowiedni do ataku na algorytm, zacznijmy od kilku ważnych obserwacji. Jak można by szukać najkrótszej ścieżki, gdyby ujemne cykle nie występowały w grafie?

Długość ścieżki

Czy najtańsza ścieżka może być bardzo długa jeśli nie ma ujemnych cykli w grafie? Zauważysz z pewnością analogię do sytuacji, gdy nie dopuszczamy wag ujemnych na krawędziach. Skoro nie ma ujemnych cykli, to nie opłaca się nam tworzyć ścieżki, która jakiś cykl zawiera. Faktycznie, można by usunąć wierzchołki z tego cyklu ze ścieżki nie psując "połączenia" między startem i celem. Ponieważ taki cykl nie był ujemny, to musiał być niedodatni - zatem jego usunięcie nie pogorszy kosztu ścieżki, a może go polepszyć.

Stąd wniosek - taka ścieżka nie może być dłuższa niż liczba wszystkich wierzchołków w grafie minus jeden (dla uproszczenia przyjmujmy od tej chwili, że liczba wszystkich wierzchołków będzie oznaczana przez $ n $). Istotnie, gdyby ścieżka przechodziła przez więcej niż $ n $ wierzchołków, jakiś wierzchołek musiałby się na niej powtórzyć - a to oznacza, że pomiędzy jego dwoma wystąpieniami jest cykl, który można z korzyścią usunąć.

Wniosek - najtańsza ścieżka, pomimo tego, że dopuszczamy krawędzie o ujemnej wadze, ma długość nie większą niż $ n-1 $, jeśli w grafie nie można z wierzchołka startowego osiągnąć cyklu ujemnego.

5
Twoja ocena: Brak Ocena: 5 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com