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 linia 1 zajmuje czas $O(|V|)$,
• w każdym z $|V|$ przebiegów głównej pętli w lini 2 algorytmu

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

• końcowa pętla algorytmu linie 5-7 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 1

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$.

Dowód

Oznaczmy przez $\delta (v,u)$ odległość z wierzchołka

$v$ do $u$ w grafie $G$. Niech $v$ będzie wierzchołkiem osiągalnym ze źródła $s$ i niech $p=(v_0,v_1,\dots ,v_k)$ oznacza najkrótszą ścieżkę z $s$ do $v$, gdzie $v_0=s$ oraz $v_k=v$. Ścieżka ta jest ścieżką prostą, bo najkrótsze ścieżki muszą być proste, więc $k\le |V|-1$. Pokażemy teraz indukcyjnie, że poczynając od $i$-tego przebiegu zachodzi $d(v_i)=\delta (s,v_i)$ dla $i=0,1,\dots ,k$. W algorytmie wykonujemy $|V|-1$ obrotów pętli oraz $k\le |V|-1$, co oznacza, że z tej tezy indukcyjnej wynika poprawność algorytmu.

Zauważmy, że teza indukcyjna zachodzi po inicjacji algorytmu, gdyż $d(v_0)=d(s)=0\delta (s,s)=\delta (s,v_0).$ Załóżmy, że teza indukcyjna zachodzi dla kroku $k$'tego. Ponieważ ścieżki $p=(v_0,v_1,\dots ,v_i)$ dla $i\le k$ są najkrótsze jako podścieżki ścieżki $p$, to po $k+1$ wykonaniu pętli wartości $d(v_i)$ dla $i\le k$ się nie zmienią. Pozostaje nam więc do pokazania to, że wartość $d(v_{k+1})$ będzie dobrze policzona. W $k+1$ przebiegu wykonujemy między innymi relaksację krawędzi $(v_k,v_{k+1})$. Ponieważ $d(v_k)$ jest dobrze policzone, to po tej relaksacji wyznaczona będzie także poprawnie wartość $d(v_{k+1})$, bo założyliśmy, że najkrótsza ścieżka do $v_{k+1}$

przechodzi przez $v_k$.

Wniosek 2

Niech $G=(V,E)$ będzie grafem skierowanym i

niech funkcja $w:E\to {ℛ}$ zadaje wagi krawędzi. Niech $d(v)$ to będą wartości wyznaczone przez algorytm Bellmana-Forda uruchomiano dla wierzchołka $s$. W $G$ istnieje ścieżka z $s$ do $v$

wtedy i tylko wtedy gdy $d(v)<\mathrm{\infty }$.

Twierdzenie 3

Niech $G=(V,E)$ będzie

grafem skierowanym i niech funkcja $w:E\to {ℛ}$ zadaje wagi krawędzi. Załóżmy, że algorytm Bellmana-Forda został wykonany dla wierzchołka $s$. Jeżeli graf nie zawiera cyklu o ujemnej wadze osiągalnego ze źródła $s$ to algorytm zwraca wartość TRUE, $d(v)$ jest odległością z $s$ do $v$, a $\pi (v)$ wyznacza drzewo najkrótszych ścieżek o korzeniu w $s$. Jeżeli natomiast $G$ zawiera cykl o ujemnej wadze osiągalny ze

źródła to algorytm zwraca wartość FALSE.

Dowód