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 {\mathcal {R}}$ przypisującą wagi krawędziom oraz jeden wybrany wierzchołek $s$. Wagę ścieżki $p=(v_{0},v_{1},\ldots ,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{cases}\min\{w(p):p{\mbox{ ścieżka z }}u{\mbox{ do }}v\},&{\mbox{jeżeli istnieje ścieżka z }}u{\mbox{ do }}v,\\\infty &{\mbox{w przeciwnym przypadku.}}\end{cases}}$

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

W problemie najkrótszych ścieżek z jednego wierzchołka chcemy obliczyć odległości $\delta (s,v)$ dla wszystkich wierzchołków $v\in V$ wraz z drzewem najkrótszych ścieżek z $s$. Drzewem najkrótszych ścieżek o korzeniu w $s$ nazywamy podgraf skierowany $G'=(V',E')$, w którym $V'\subseteq V$, $E'\subseteq E$ taki, że:

• $V'$ jest zbiorem wierzchołków w $G$ do których istnieje ścieżka z $s$,
• $G'$ jest drzewem którego korzeniem jest $s$,
• dla każdego wierzchołka $v\in V'$ jedyna ścieżka z $s$ do $v$ w grafie $G'$ jest najkrótszą ścieżką z $s$ do $v$ w grafie $G$.

W naszych algorytmach drzewo najkrótszych ścieżek będziemy reprezentować jako funkcję poprzedników $\pi :V\to V$, określającą poprzednika wierzchołka $v$ w drzewie najkrótszych ścieżek. Drzewo najkrótszych ścieżek $G_{\pi }=(V_{\pi },E_{\pi })$ możemy uzyskać z $\pi$ w następujący sposób:

$V_{\pi }=\{v\in V:\pi (v)\neq NIL\}\cup \{s\},$

$E_{\pi }=\{(\pi (v),v)\in E:v\in V_{\pi }-\{s\}\}.$

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 {\mathcal {R}}$. 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 istnieje, algorytm oblicza najkrótsze ścieżki z $s$ do wszystkich pozostałych wierzchołków wraz z ich wagami.

Relaksacja

Podobnie jak to było w Algorytmie Dijkstry, użyjemy metody relaksacji. W metodzie tej utrzymujemy dla każdego wierzchołka $v\in V$ wartość $d(v)$, będącą górnym ograniczeniem wagi najkrótszej ścieżki z $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)$
 1  for każdy wierzchołek $v\in V$ do
 2  begin
 3    $d(v)=\infty$
 4    $\pi (v)=NIL$
 5  end
 6  $d(s)=0$
 7  return $(d,\pi )$

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

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 następującej procedury nazwanej tutaj RELAKSUJ.

Algorytm Relaksacja krawędzi

---

 RELAKSUJ$(u,v,w,d,\pi )$
 1  if $d(v)>d(u)+w(u,v)$ then
 3  begin
 4    $d(v)=d(u)+w(u,v)$
 5    $\pi (v)=u$
 6  end

Algorytm

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

Algorytm Bellmana-Forda

---

 BELLMAN-FORD$(G,w,s)$
 1  $(d,\pi )=$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,d,\pi )$
 5  for każda krawędź $(u,v)\in E$ do
 6    if '$d(v)>d(u)+w(u,v)$ then
 7      return $NIL$
 8  return $(d,\pi )$

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

<flash>file=Zasd_animacja_bellman_ford1.swf|width=660|height=250</flash>

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

• proces inicjacji w linii 1 zajmuje czas $O(|V|)$,
• w każdym z $|V|$ przebiegów głównej pętli w linii 2 algorytmu przeglądane są wszystkie krawędzie grafu w linii 3 , co zajmuje czas $O(|V||E|)$,
• końcowa pętla algorytmu w liniach 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 {\mathcal {R}}$ 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},\ldots ,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\leq |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,\ldots ,k$. W algorytmie wykonujemy $|V|-1$ obrotów pętli oraz $k\leq |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$ i $\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},\ldots ,v_{i})$ dla $i\leq 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\leq 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, 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)=\infty$ pod koniec działania algorytmu. Gdyby tak nie było, oznaczałoby to, z właściwości procedury RELAKSUJ, że istnieje ścieżka od $s$ do $v$, co daje sprzeczność.

Twierdzenie 2

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

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, która wyliczając odległość wyznacza 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, 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)\leq \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 nie zwróci $NIL$.

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},\ldots ,v_{k})$, gdzie $v_{0}=v_{k}$. Dla cyklu tego mamy:

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

Gdyby w tej sytuacji algorytm Bellmana-Forda nie zwrócił wartości $NIL$, 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})\geq d(v_{i+1})$. Sumując tę nierówność stronami po wszystkich $i=0,\ldots ,k-1$, otrzymujemy:

$\sum _{i=0}^{k-1}\left[d(v_{i})+w(v_{i},v_{i+1})\right]\geq \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})\geq \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})\geq \sum _{i=0}^{k-1}d(v_{i}).$

Wiemy, że cykl $c$ jest osiągalny z $s$, a zatem dla każdego $i=0,\ldots ,k$ mamy $d(v)<\infty$. Możemy więc skrócić $\sum _{i=0}^{k-1}d(v_{i})$ po obydwu stronach nierówności otrzymując:

$\sum _{i=0}^{k-1}w(v_{i},v_{i+1})\geq 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 $NIL$.