Algorytm Bellmana-Forda

03.10.2010 - Damian Rusak
TrudnośćTrudność

Jak to wykorzystać?

No tak, ale skąd mamy z góry wiedzieć, które krawędzie należą do interesujących nas najtańszych ścieżek? Otóż nie wiemy tego i aby mieć pewność, że zrelaksujemy te krawędzie, które potrzeba, relaksujemy wszystkie krawędzie!

Zauważ, że jeśli zrelaksujemy wszystkie krawędzie jeden raz, wszystkie wierzchołki, do których najkrótsze ścieżki mają długość 1 otrzymały w tym momencie najtańsze połączenie. Czemu więc nie zrelaksować wszystkich krawędzi jeszcze raz! Wtedy te wierzchołki, których najtańsze ścieżki mają długość 2 zostaną obdarzone najtańszym połączeniem - musiała do każdego z nich wchodzić pewna krawędź od wierzchołka, któremu pierwsza relaksacja ustaliła najlepszą odległość. Jeśli zrobimy to trzeci raz... ale ile razy wystarczy?

Pamiętasz, jak ustaliliśmy, że jeśli w grafie nie występuje cykl ujemny, to każda najtańsza ścieżka jest nie dłuższa niż $ n-1 $? W takim razie jeśli wykonamy $ n-1 $ kroków relaksacji, każdy wierzchołek otrzyma najtańsze połączenie! Któryś z kolejnych kroków będzie krokiem odpowiadającym długości najkrótszej ścieżki do tego wierzchołka i przypisze mu najlepszą odległość.

Zauważ, że przedostatnia animacja przedstawia właśnie kolejne kroki relaksacji. Oznaczone są tam te krawędzie, które warto relaksować (ich relaksacja poprawia odległość do wierzchołka na ich końcu).

To może wydawać się czasochłonne - krawędzi może być nawet rzędu $ n^{2} $. Lecz okazuje się, że jest to koszt, który trzeba ponieść - jest to jeden z najlepszych algorytmów rozwiązujących nasz problem.

Wykrywanie ujemnych cykli

Co z naszym drugim postulatem - wykryciem ujemnych cykli? Zauważ, że cały czas zakładaliśmy, że takie nie występują i wtedy faktycznie wszystkie powyższe obserwacje są prawdziwe. Co jednak jeśli można osiągnąć cykl ujemny z wierzchołka początkowego? 

Pomyślmy, co by się wydarzyło, jeśli wykonalibyśmy krok relaksacji wszystkich krawędzi jeszcze $ n $-ty raz... Jeśli w grafie nie było cykli ujemnych, to te relaksacje nic nie zmienią - pokazaliśmy, że $ n-1 $ kroków relaksacji wystarczy, by uzyskać najlepsze odległości dla wszystkich wierzchołków. Ale co, jeśli okaże się, że w dalszym ciągu można poprawić jakiemuś wierzchołkowi odległość? To oznaczałoby, że istnieje wierzchołek, któremu "opłaca się" ścieżka dłuższa niż $ n-1 $ - ale wtedy (zgodnie z jedną naszych obserwacji), musi się w tej ścieżce zawierać cykl ujemny!

Ponadto, jeśli taki cykl jest osiągalny, to znajdziemy jakiś wierzchołek, któremu $ n $-ta relaksacja pomoże -uzasadnienie pozostawimy Ci jako ćwiczenie.

Animacja poniżej przedstawia sytuację, w której cykl ujemny zostaje wykryty!

 

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

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com