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.

Definicja problemu

W wykładzie tym zajmiemy się problemem obliczania najkrótszych ścieżek w grafie wychodzących z jednego wierzchołka. Załóżmy, że mamy dany graf $G=(V,E)$, funkcję $w:E\to {ℛ}$ przypisującą wagi krawędziom oraz jeden wybrany wierzchołek $s$. Wagę ścieżki $p=(v_0,v_1,\dots ,v_k)$ definiujemy jako wagę tworzących ją krawędzi:

$w(p)=\sum _{i=0}^{k-1}w(v_i,v_{i+1}).$

Odległość z wierzchołka $u$ do wierzchołka $v$ definiujemy jako

$\delta (u,v)=\{\begin{array}{ll}\min \{w(p):p\text{ ścieżka z }u\text{ do }v\},& \text{jeżeli istnieje ścieżka z }u\text{ do }v,\\ \mathrm{\infty }& \text{w przeciwnym przypadku.}\end{array}$

Najkrótszą ścieżką z wierzchołka $u$ do wierzchołka $v$ jest każda ścieżka $p$ z $u$ do $v$, której waga $w(p)$jest równa odległości $\delta (u,v)$ z $u$ do $v$.

Historia Problemu

W dalszej części tego wykładu zajmiemy się przedstawieniem algorytm Bellmana-Forda, który jest jednym z kilku kilku rozwiązań dla problemu obliczania najkrótszych ścieżek z jednego wierzchołka w grafie. Metoda ta jest oparta na dwóch oddzielnych algorytmach podanych przez Bellmana oraz Forda Bellman opisał związek między problemem najkrótszych ścieżek a problemem ograniczeń liniowych (zobacz Zadania 1), natomiast Ford podał jak rozwiązać ten drugi problem. Algorytm Bellmana-Forda działa jest najszybszym znany algorytmem w pełni wielomianowych. Jest znane kilka algorytmów szybszych, które działają jednak tylko w przypadku całkowitoliczbowych wag krawędzi, a ich złożoność zależy od maksymalnej wagi krawędzi w grafie. Wszystkie te algorytmy przedstawione są w poniższej tabeli. Co ciekawe mimo, że jest to jeden z najbardziej klasycznych problemów algorytmiki, to jest on nadal żywy i najnowsze z tych algorytmów powstały w ostatnich latach.

Znane algorytmy dla problemu obliczania najkrótszych ścieżek z jednego wierzchołka

Complexity	Author
$O(n^4)$	Shimbel (1995)
$O(nm)$	Ford (1956), Bellman (1958)
$O(n^{\frac{3}{4}}m\log W)$	Gabow (1983)
$O(\sqrt{n}m\log (nW))$	Gabow and Tarjan (1989)
$O(\sqrt{n}m\log (W))$	Goldberg (1993)
$\tilde{O}(n^{\omega }W)$	Yuster and Zwick (2005), Sankowski (2005)

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 Inicjacja algorytmu najkrótszych ścieżek

---

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

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

Poprawność

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

Pozostaje nam jedynie zastanowić się co się dzieje gdy wierzchołek $v$ nie jest osiągalny z $s$. Musi wtedy zachodzić $d(v)=\mathrm{\infty }$ pod koniec działania algorytmu. Gdyby tak nie było to oznaczało by, z właściwości procedury RELAKSUJ, że istnieje ścieżka od $s$ do $v$. Sprzeczność.

Dowód

Dowód ten można przeprowadzić w podobny sposób do dowodu lematu Lematu 1.

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

Załóżmy najpierw, że graf nie zawiera cykli o ujemnej wadze, które byłyby osiągalne z $s$. Wtedy z Lematu 1 wiemy, że $d(v)$ są poprawnie policzonymi odległościami. Jeżeli odległości $d(v)$ zostały poprawnie policzone przez funkcję RELAKSUJ to $\pi (v)$ koduje najkrótsze ścieżki w grafie. Wynika to z właściwości funkcji RELAKSUJ relaks, która wyliczając odległość wyznaczą jednocześnie przez jaki wierzchołek prowadzi ta najkrótsza ścieżka.

Musimy teraz pokazać, że algorytm poprawnie wykrywa, czy w grafie $G$ istnieje cykl ujemnej długości osiągalny z $s$. Jeżeli nie ma takiego cyklu to wtedy $d(v)$ są poprawnie policzone przed wykonaniem testu w liniach 5-8 algorytmu Bellmana-Forda. W takim razie zachodzi:

$d(v)=\delta (s,v)\le \delta (s,u)+w(u,v)=d(u)+w(u,v).$

Powyższa nierówność zachodzi ponieważ $s\to u\to v$ jest ścieżką w grafie, a więc jest nie krótsza niż najkrótsza ścieżka $s\to v$. Widzimy więc, że w tym przypadku żaden z testów w linijce 6 algorytmu nie będzie spełniony i algorytm zwróci TRUE.

Załóżmy teraz, że w grafie $G$ istnieje cykl o ujemnej wadze osiągalny z $s$. Oznaczmy ten cykl jako $c=(v_0,v_1,\dots ,v_k)$, gdzie $v_0=v_k$. Dla cyklu tego mamy:

$\sum _{i=0}^{k}w(v_i,v_{i+1})<0.$      (1)

Gdyby w tej sytuacji algorytm Bellmana-forda zwrócił wartość TRUE to dla każdej krawędzi $(v_i,v_{i+1})$ musiałaby zachodzić nierówność $d(v_i)+w(v_i,v_{i+1})\ge d(v_{i+1})$. Sumując tą nierówność stronami po wszystkich $i=0,\dots ,k-1$ otrzymujemy.

$\sum _{i=0}^{k-1}[d(v_i)+w(v_i,v_{i+1})]\ge \sum _{i=0}^{k-1}d(v_{i+1}),$ $\sum _{i=0}^{k-1}d(v_i)+\sum _{i=0}^{k-1}w(v_i,v_{i+1})\ge \sum _{i=1}^{k}d(v_i),$

ponieważ $v_0=v_k$ to

$\sum _{i=0}^{k-1}d(v_i)+\sum _{i=0}^{k-1}w(v_i,v_{i+1})\ge \sum _{i=0}^{k-1}d(v_i).$

Wiemy, że cykl $c$ jest osiągalny a zatem dla każdego $i=0,\dots ,k$ mamy $d(v)<\mathrm{\infty }$. Możemy więc skrócić $\sum _{i=0}^{k-1}d(v_i)$ po obydwu stronach równania i otrzymujemy:

$\sum _{i=0}^{k-1}w(v_i,v_{i+1})\ge 0,$

co stoi w sprzeczności z nierównością (1). Jeżeli więc w grafie istnieje cykl o ujemnej wadze osiągalny z $s$, to algorytm zwróci FALSE.

-->