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' 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^{\prime }=(V^{\prime },E^{\prime })$ możemy uzyskać z $\pi$ w następujący sposób:

$V^{\prime }=\{v\in V:\pi (v)\ne NIL\}\cup \{s\},$ $E^{\prime }=\{(\pi (v),v)\in E:v\in V_{\pi }-\{s\}\}.$

Historia Problemu

W dalszej części tego wykładu zajmiemy się przedstawieniem algorytmu Bellmana-Forda, który jest jednym z 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 jest najszybszym znanym algorytmem w pełni wielomianowym. Istnieje kilka szybszych algorytmów, 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

Złożoność	Autor
$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)
$O(n^{2.38}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 istnieje 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)$
 1  for każdy wierzchołek $v\in V$ do
 2    $d(v)=\mathrm{\infty }$
 3    $\pi (v)=NIL$
 4  $d(s)=0$
 5  return $(d,\pi )$

Ustalone przez tą procedurę 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,d,\pi )$
   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 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.

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\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łoby, 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 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 zawiera cyklu 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$.

{{dowod|||3=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 [[#algorytm_relaksacja_krawędzi|funkcji RELAKSUJ], 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 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}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 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 NIL. }}