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

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^{\prime }=(V^{\prime },E^{\prime })$, w którym $V^{\prime }\subseteq V$, $E^{\prime }\subseteq E$ taki, że:

• $V^{\prime }$ jest zbiorem wierzchołków w $G$ do których istnieje ścieżka z $s$,
• $G^{\prime }$ jest drzewem którego korzeniem jest $s$,
• dla każdego wierzchołka $v\in V^{\prime }$ jedyna ścieżka z $s$ do $v$ w grafie $G^{\prime }$ 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)\ne 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 {ℛ}$. 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)=\mathrm{\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 {ℛ}$ 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$ 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,\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, 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, 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 {ℛ}$ 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)\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 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,\dots ,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})\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 z $s$, 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 nierówności otrzymując:

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