Zaawansowane algorytmy i struktury danych/Wykład 5

Abstrakt

Pierwsza część tego wykładu poświęcona będzie problemowi obliczania najkrótszych ścieżek w grafie z jednego źródła w przypadku, w którym wagi krawędzi mogą być ujemne. Zaprezentujemy algorytm Bellmana-Forda, który rozwiązuje ten problem w czasie $O(|V||E|)$. W drugiej części zajmiemy się problemem obliczania odległości między wszystkimi parami wierzchołków. Pokażemy związki tego problemu z mnożeniem macierzy.

Algorytm Bellmana-Forda

Algorytm Bellmana-Forda służy do rozwiązania problemu znalezienia najkrótszych ścieżek w grafie, w którym wagi krawędzi mogą być ujemne. W problemie tym mamy dany graf $G=(V,E)$ i funkcję wagową $w:E\to {ℛ}$. Algorytm Bellmana-Forda wylicza dla zadanego wierzchołka $s$, czy istnieje w grafie $G$ cykl o ujemnej wadze osiągalny z $s$. Jeżeli taki cykl nie istniej to algorytm oblicza najkrótsze ścieżki z $s$ do wszystkich pozostałych wierzchołków wraz z ich wagami.

Relaksacja

Podobnie ja to było w Algorytmie Dijkstry użyjemy metody relaksacji. Metoda ta polega na tym, że w trakcie działania algorytmu dla każdego wierzchołka $v\in V$ utrzymujemy wartość $d(v)$ będącą górnym ograniczeniem wagi najkrótszej ścieżki ze $s$ do $v$. W algorytmie utrzymywać będziemy także dla każdego wierzchołka $v$ wskaźnik $\pi (v)$ wskazujący na poprzedni wierzchołek przez, który prowadzi dotychczas znaleziona najkrótsza ścieżka. Na początku wielkości te inicjujemy przy pomocy następującej procedury:

Algorytm Inicjalizacja algorytmu najkrótszych ścieżek

---

 INICJALIZUJ$(G,s)$
   for każdy wierzchołek $v\in V$ do
     $d(v)=\mathrm{\infty }$
     $\pi (v)=NIL$
   $d(s)=0$

Ustalone przez tą procedure wartości $d(v)$ są dobrymi ograniczeniami górnymi na odległości.

Relaksacja krawędzi $(u,v)$ polega na sprawdzeniu, czy przechodząc krawędzią $(u,v)$ z $u$ do $v$, nie otrzymamy krótszej ścieżki z $s$ do $v$niż ta dotychczas znaleziona. Jeżeli tak to aktualizowane są także wartości $d(v)$ i $\pi (v)$. W celu relaksacji krawędzi $(u,v)$ używamy procedury RELAKSUJ.

Algorytm Relaksacja krawędzi

---

 RELAKSUJ$(u,v,w)$
   if $d(v)>d(u)+w(u,v)$ then
     $d(v)=d(u)+w(u,v)$
     $\pi (v)=u$

Algorytm

Po przypomnieniu czym była relaksacja gotowi jesteśmy na zapisanie algorytm Bellmana-Forda, a następnie udowodnienie jego poprawności.

Po przypomnieniu czym była relaksacja gotowi jesteśmy na zapisanie algorytm Bellmana-Forda, a następnie udowodnienie jego poprawności.

Algorytm Bellmana-Forda

---

 BELLMAN-FORD$(G,w,s)$
 1  INICJUJ$(G,s)$
 2  for $i=1$ to $|V|-1$ do
 3    for każda krawędź $(u,v)\in E$ do
 4      RELAKSUJ$(u,v,w)$
 5  for każda krawędź $(u,v)\in E$ do
 6    if '$d(v)>d(u)+w(u,v)$ then
 7      return FALSE
 8  return TRUE

Poniższa animacja przedstawia działanie algorytmu dla grafu o pięciu wierzchołkach.

Algorytm ten działa w czasie $O(|V||E|)$, co jest łatwo pokazać gdyż:

• proces inicjacji zajmuje czas $O(|V|)$,
• w każdym z $|V|$ przebiegów głównej pętli algorytmu

przeglądane są wszystkie krawędzie grafu, co zajmuje czas $O(|V||E|)$,

• końcowa pętla algorytmu działa w czasie $O(|E|$.

Dowód poprawności algorytmu Bellmana-Forda zaczniemy od pokazania, że algorytm działa poprawnie przy założeniu, że w grafie nie ma cykli o ujemnych wagach.

Lemat

Niech $G=(V,E)$ będzie grafem skierowanym i niech funkcja $w:E\to {ℛ}$ zadaje wagi krawędzi. Niech $s$ będzie wierzchołkiem z którego liczymy odległości algorytmem Bellmana-Forda. Jeżeli w grafie nie ma cykli o ujemnej wadze osiągalnych z $s$, to algorytm poprawnie oblicza odległości, tzn. na koniec działania algorytmu dla każdego $v\in V$ wartość $d(v)$ jest odległością w $G$ z $s$ do $v$.