Zaawansowane algorytmy i struktury danych/Wykład 6

Abstrakt

W wykładzie tym zajmiemy się problemem obliczania odległości w grafie między wszystkimi parami wierzchołków w grafie ważonym skierowanym $G=(V,E)$. Przedstawimy trzy algorytmy rozwiązujące ten problem:

• algorytm wykorzystujący mnożenie macierzy, działający w czasie $O(|V|^{3}\log |V|)$,
• algorytm Floyda-Warshalla, działający w czasie $O(|V|^{3})$,
• algorytm Johnsona, działający w czasie $O(|V|^{2}\log |V|+|V||E|)$.

Problem najkrótszych ścieżek między wszystkimi parami wierzchołków

Problem najkrótszych ścieżek między wszystkimi parami wierzchołków można rozwiązać, wykonując $|V|$ razy algorytm dla problemu najkrótszych ścieżek z jednego wierzchołka. Jeżeli w grafie wagi krawędzi są nieujemne to możemy użyć algorytmu Dijkstry. Najszybsza implementacja algorytmu Dijskstry wykorzystująca kopce Fibonacciego działa w czasie $O(|V|\log |V|+|E|)$, co daje nam algorytm rozwiązujący problem policzenia odległości między wszystkimi parami wierzchołków, działający w czasie $O(|V|^{2}\log |V|+|V||E|)$.

Jednakże tego rozwiązania nie możemy użyć, jeżeli w grafie wagi krawędzi mogą być ujemne. W takim przypadku możemy użyć algorytm Bellmana-Forda. Otrzymamy wtedy algorytm działający w czasie $O(|V|^{2}|E|)$. W rozdziale tym zaprezentujemy bardziej efektywne rozwiązania dla tego problemu.

W rozdziale tym będziemy zakładać, że algorytmy na wejściu otrzymują macierz wag $W$ rozmiaru $n\times n$ reprezentującą wagi krawędzi $n$-wierzchołkowego grafu $G=(V,E)$. Dla macierzy tej zachodzi:

$w_{i,j}={\begin{cases}0,&{\mbox{jeśli }}i=j,\\{\mbox{waga krawędzi }}(i,j),&{\mbox{jeśli }}i\neq j{\mbox{ i }}(i,j)\in E,\\\infty ,&{\mbox{jeśli }}i\neq j{\mbox{ i }}(i,j)\neq E.\end{cases}}$

W problemie najkrótszych ścieżek między wszystkimi parami wierzchołków chcemy wyznaczyć macierz $D$ rozmiaru $n\times n$, taką że $d_{i,j}$ jest równe odległości $\delta (i,j)$ z wierzchołka $i$ do wierzchołka $j$. Chcemy także wyznaczyć dla każdego wierzchołka $v$ drzewo najkrótszych ścieżek $T_{v}$ ukorzenione w $v$. Podobnie jak w poprzednim rozdziale drzewo $T_{v}$ możemy kodować dla każdego wierzchołka przy pomocy funkcji poprzedników $\pi _{v}$. Ponieważ tutaj interesuje nas wiele drzew, łatwiej będzie nam używać macierzy poprzedników $\Pi$. Macierz tą definiujemy używając funkcji $\pi _{v}$ w następujący sposób:

$\Pi _{v,u}=\pi _{v}(u).$

W pozostałej części tego wykładu zajmiemy się tylko wyznaczaniem macierzy odległości $D$. Zadaniu 3 do tego wykładu polega na pokazaniu, jak znając odległości w grafie policzyć drzewo najkrótszych ścieżek w czasie $O(|E|)$. Tak więc $|V|$ drzew możemy wyliczyć w czasie $O(|E||V|)$. Czas ten jest mniejszy niż czas działania wszystkich prezentowanych w tym wykładzie algorytmów, więc bez straty ogólności, a zyskując na prostocie prezentacji, możemy ograniczyć się tylko do wyznaczenia macierzy odległości $D$.

Co więcej, będziemy zakładać, że w grafie nie ma ujemnych cykli. Ujemne cykle można wykryć w czasie $O(|V||E|)$ przy użyciu Algorytmu Bellmana-Forda. Zobacz Zadanie 3 do Wykładu 4.

Najkrótsze ścieżki i mnożenie macierzy

Iloczyn odległości i jego właściwości

Załóżmy, że dane mamy dwie macierze wag $C$ oraz $D$ rozmiaru $n\times n$. Dla macierzy tych definiujemy operację $\times _{\min }$ iloczyn odległości, której wynikiem jest także macierz rozmiaru $n\times n$, zdefiniowana jako:

$(C\times _{\min }D)_{i,j}=\min _{k=1,\ldots ,n}C_{i,k}+D_{k,j}.$      (1)

Wniosek 1

Jeżeli założymy, że $C$ i $D$ opisują minimalne wagi zbioru ścieżek odpowiednio $\Pi _{C}$ i $\Pi _{D}$ w pewnym grafie $G$, to iloczyn odległości wyznacza minimalne wagi zbioru ścieżek powstałego z konkatenacji ścieżek ze zbioru $\Pi _{C}$ ze ścieżkami ze zbioru $\Pi _{D}$.

Wniosek ten jest przedstawiony na poniższej animicji, gdzie zostały zaznaczone dwa zbiory ścieżek, pierwszy, zaznaczony na zielono, reprezentowany przez macierz $A$ oraz graf $G_{A}$, oraz drugi, zaznaczony na niebiesko, reprezentowany przez macierz $B$ oraz graf $G_{B}$. W wyniku wykonania mnożenia otrzymujemy macierz $C$ oraz graf $G_{C}$ <flash>file=Zasd_ilustr_f.swf|width=600|height=500</flash>

Pokażemy teraz, że produkt odległości jest operacją łączną.

Lemat 2

Dla macierzy $C$, $D$ i $E$ rozmiaru $n\times n$ zachodzi:

$\left(C\times _{\min }D\right)\times _{min}E=C\times _{\min }\left(D\times _{min}E\right).$

Dowód

Powyższa równość wynika wprost z wzoru (1) oraz przemienności operacji $\min$.

Co więcej, produkt odległości jest przemienny względem dodawania.

Lemat 3

Dla macierzy $C$, $D$ i $E$ rozmiaru $n\times n$ zachodzi:

$C\times _{\min }\left(D+E\right)=C\times _{\min }D+C\times _{min}E,$

oraz

$\left(D+E\right)\times _{\min }C=D\times _{\min }C+E\times _{min}C.$

Dowód

Te dwie równości wynikają ponownie z wzoru (1) oraz przemienności operacji $\min$ względem dodawania.

Zdefiniujmy macierz $I_{\min }$ rozmiaru $n\times n$ jako:

$\left(I_{\min }\right)_{i,j}={\begin{cases}0,&{\mbox{jeśli }}i=j,\\\infty ,&{\mbox{jeśli }}i\neq j.\end{cases}}$

Macierz ta jest jedynką dla iloczynu odległości.

Lemat 4

Dla macierzy $C$ rozmiaru $n\times n$ zachodzi:

$I_{\min }\times _{\min }C=C\times _{\min }I_{\min }=C.$

Dowód

Mamy

$\left(I_{\min }\times _{\min }C\right)_{i,j}=\min _{k=1,\ldots ,n}\left(I_{\min }\right)_{i,k}+C_{k,j}=$

ponieważ wszystkie elementy $\left(I_{\min }\right)_{i,k}$ równe są $\infty$ oprócz elementu $i=k$, możemy je pominąć w operacji $\min$ i:

$=\min _{k=i}\left(I_{\min }\right)_{i,k}+C_{k,j}=I_{i,i}+C_{i,j}=C_{i,j}.$

Pomysł algorytmu

Łączność iloczynu odległości ma dla nas bardzo ważne konsekwencje i pozwoli nam na konstrukcję algorytmu obliczania odległości w grafie między wszystkimi parami wierzchołków, działającego w czasie $O(|V|^{3}\log |V|)$. Niech $W$ będzie macierzą wag grafu $G=(V,E)$. Rozważmy macierz $W^{m}$ zdefiniowaną jako:

$W^{m}={\begin{cases}I_{\min },&{\mbox{jeżeli }}m=0,\\W\times _{\min }W^{m-1},&{\mbox{jeżeli }}m>0.\end{cases}}$

Pokażemy teraz, że macierz $W^{m}$ opisuje odległości między wierzchołkami grafu, ale tylko dla ścieżek używających nie więcej niż $m$ krawędzi.

Lemat 5

Element $W_{i,j}^{m}$ macierzy $W^{m}$ zadaje najmniejszą wagę ścieżki, wychodzącej z wierzchołka $i$ do wierzchołka $j$ spośród ścieżek, które zawierają nie więcej niż $m$ krawędzi, tzn.:

$w_{i,j}^{m}={\begin{cases}\min\{w(p):p{\mbox{ ścieżka o długości }}\leq m{\mbox{ z }}u{\mbox{ do }}v\},&{\mbox{jeżeli istnieje ścieżka o długości }}\leq m{\mbox{ z }}u{\mbox{ do }}v,\\\infty &{\mbox{w przeciwnym przypadku.}}\end{cases}}$

Dowód

Tezę tę udowodnimy przez indukcję po $m$. Ścieżki używające $0$ krawędzi istnieją tylko z każdego wierzchołka do niego samego i mają długość $0$, a więc dla $m=0$ teza wynika wprost z definicji macierzy $W^{0}$. Załóżmy teraz, że teza zachodzi dla $m>0$. Mamy wtedy $W^{m+1}=W\times _{\min }W^{m}$. Zauważmy, że definicja macierzy wag $W$ opisuje ścieżki używające $\leq 1$ krawędź. Korzystając teraz z Wniosku 1 otrzymujemy tezę dla $m+1$.

Zajmiemy się teraz konstrukcją algorytmu obliczającego najkrótsze ścieżki w grafie. W tym celu będziemy musieli jeszcze udowodnić następujące dwa lematy.

Lemat 6

Jeżeli w grafie $G=(V,E)$, w którym wagi krawędzi zadane są macierzą $W$ nie istnieje cykl o ujemnej wadze to:

$\delta (u,v)=W_{u,v}^{(k)},{\mbox{ dla }}k\geq n-1.$

Dowód

Jeżeli w grafie nie istnieje cykl o ujemnej wadze, to wszystkie najkrótsze ścieżki są ścieżkami prostymi, a więc mają długość co najwyżej $n-1$. Z Lematu 5 wynika więc, że odległości tych ścieżek są dobrze wyznaczone w $W^{k}$ dla $k\geq n-1$.

Algorytm

Zauważmy, że iloczyn odległości dwóch macierzy możemy policzyć w czasie $O(|V|^{3})$ wykorzystując następujący algorytm.

Algorytm Mnożenia macierzy odległości

---

 MNOŻENIE-ODLEGŁOŚCI$(C,D)$
 1  $E$ macierz rozmiaru $n\times n$
 2  for $i=0$ to $n-1$ do
 3    for $j=0$ to $n-1$ do
 4    begin
 5      $e_{i,j}=\infty$
 6      for $k=0$ to $n-1$ do
 7        $e_{i,j}=\min(c_{i,k}+d_{k,j},e_{i,j})$
 8    end
 9  return E

Ponieważ operacja iloczynu odległości jest łączna, możemy wykorzystać algorytm szybkiego potęgowania i policzyć odległości przy pomocy następującego algorytmu.

Algorytm Algorytm obliczania odległości między wszystkimi parami wierzchołków I

---

 ODLEGŁÓŚCI-I$(W)$
 1  $D=W$
 2  $m=1$
 3  while $n-1>m$ do
 4  begin
 5    $D=$MNOŻENIE-ODLEGŁOŚCI$(D,D)$
 6    $m=2m$
 7  end
 8  return $D$

Poprawność tego algorytmu wynika wprost z Lematu 6 ponieważ na zakończenie algorytmu $D=W^{m}$ i $m>n-1$.

Algorytm Floyda-Warshalla

W algorytmie Floyda-Warshalla wykorzystamy inną cechę najkrótszych ścieżek niż ta użyta w algorytmie z wykorzystaniem iloczynu odległości. W poprzednim algorytmie konstruowaliśmy coraz dłuższe ścieżki, natomiast tutaj będziemy konstruować ścieżki przechodzące przez coraz większy zbiór wierzchołków. Wierzchołkiem wewnętrznym ścieżki $p=(v_{0},\ldots ,v_{l})$ jest każdy wierzchołek na ścieżce $p$ różny od jej początku $v_{0}$ i końca $v_{l}$.

Niech zbiorem wierzchołków grafu $G$ będzie $V=\{1,\ldots ,n\}$. Niech $d_{i,j}^{(k)}$ dla $k=0,\ldots ,n$ oznacza najmniejszą wagę ścieżki z $i$ do $j$ spośród ścieżek, których wierzchołki wewnętrzne należą do zbioru $\{1,\ldots ,k\}$. Pokażemy następujący rekurencyjny wzór na $D^{(k)}$.

Lemat 7

Dla $k=0,\ldots ,n$ zachodzi:

$d_{i,j}^{(k)}={\begin{cases}w_{i,j},&{\mbox{jeżeli }}k=0,\\\min(d_{i,j}^{(k-1)},d_{i,k}^{(k-1)}+d_{k,j}^{(k-1)}),&{\mbox{jeżeli }}k\geq 1.\end{cases}}$      (2)

Dowód

Dla $k=0$ poprawność powyższego wzoru wynika bezpośrednio z definicji $D^{0}$. Dla $k>0$ musimy pokazać, że

$d_{i,j}^{(k)}=\min(d_{i,j}^{(k-1)},d_{i,k}^{(k-1)}+d_{k,j}^{(k-1)}).$

Niech $p$ będzie najkrótszą ścieżką z $i$ do $j$, której wierzchołki wewnętrzne należą do zbioru $\{v_{1},\ldots ,v_{k}\}$. Mamy dwa przypadki:

• Wierzchołek $v_{k}$ nie leży na ścieżce $p$. Wtedy zachodzi $d_{i,j}^{(k)}=p(w)=d_{i,j}^{(k-1)}$. Ponieważ $p$ jest najkrótszą ścieżką, to także $p(w)\leq d_{i,k}^{(k-1)}+d_{k,j}^{(k-1)}$ i powyższy wzór zachodzi.
• Jeżeli wierzchołek $v_{k}$ należy do ścieżki $p$, to występuje on dokładnie raz i możemy podzielić $p$ na dwie ścieżki $p_{1}$ z $i$ do $k$ oraz $p_{2}$ z $k$ do $j$. Ścieżki $p_{1}$ i $p_{2}$ nie zawierają wierzchołka $v_{k}$ jako wierzchołka wewnętrznego. Ponieważ są to podścieżki najkrótszej ścieżki, więc same też są najkrótsze. Zachodzi więc dla nich $w(p_{1})=d_{i,k}^{(k-1)}$ oraz $w(p_{2})=d_{k,j}^{(k-1)}$. Otrzymujemy więc $d_{i,j}^{(k)}=w(p)=w(p_{1})+w(p_{2})=d_{i,k}^{(k-1)}+d_{k,j}^{(k-1)}$. Ponieważ $p$ jest najkrótszą ścieżką, $p(w)\leq d_{i,j}^{(k-1)}$ i wzór zachodzi także w tym przypadku.

Wykorzystując wzór (2) możemy skonstruować następujący algorytm, obliczający w czasie $O(|V|^{3})$ odległości między wszystkimi parami wierzchołków.

Algorytm Algorytm Floyda-Warshalla

---

 ODLEGŁÓŚCI-II$(W)$
 1  $D^{(0)}=W$,
 2  for $k=1$ to $n$ do
 3    for $i=1$ to $n$ do
 4      for $j=1$ to $n$ do
 5        $d_{i,j}^{(k)}=\min(d_{i,j}^{(k-1)},d_{i,k}^{(k-1)}+d_{k,j}^{(k-1)})$
 6  return $D^{(n)}$

Algorytm Johnsona

W algorytmie Johnsona wykorzystamy spostrzeżenie uczynione przez nas na początku wykładu, że odległości w grafie, w którym wszystkie wagi krawędzi są dodatnie, można obliczyć korzystając z algorytmu Dijkstry w czasie $O(|V|^{2}\log |V|+|V||E|)$. Pokażemy tutaj, jak zmienić wagi w grafie tak, aby stały się one dodatnie, przy zachowaniu najkrótszych ścieżek.

Niech będzie dany graf skierowany $G=(V,E)$ wraz z funkcją wagową $w:E\to {\mathcal {R}}$. Niech funkcja $h:V\to {\mathcal {R}}$ będzie dowolną funkcją ze zbioru wierzchołków w liczby rzeczywiste. Dla funkcji $h$ oraz $w$ definiujmy nową funkcję wagową oznaczoną $w_{h}$ w następujący sposób:

$w_{h}(u,v)=w(u,v)+h(u)-h(v).$      (3)

Oznaczmy, przez $\delta (u,v)$ odległości w grafie $G$ dla funkcji wagowej $w$ oraz przez $\delta _{h}(u,v)$ odległości w grafie $G$ dla funkcji wagowej $w_{h}$.

Lemat 8

Dla funkcji $w$, $w_{h}$ oraz dowolnej ścieżki $p=(v_{0},\ldots ,v_{k})$ zachodzi:

$w_{h}(p)=w(p)+h(v_{0})-h(v_{k}).$

Dowód

Mamy:

$w_{h}(p)=\sum _{i=0}^{k-1}w_{h}(v_{i},v_{i+1})=$

$=\sum _{i=0}^{k-1}\left(w(v_{i},v_{i+1})+h(v_{i})-h(v_{i+1})\right)=$

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

$=w(p)+h(v_{0})-h(v_{k}).$

Widzimy więc, że zmiana długości ścieżki zależy tylko od jej końców. Otrzymujemy stąd wprost dwa wnioski.

Wniosek 9

Dla funkcji $w$, $w_{h}$, oraz dowolnej pary wierzchołków zachodzi:

$\delta _{h}(u,v)=\delta (u,v)+h(u)-h(v).$

Wniosek 10

Ścieżka $p$ z wierzchołka $u$ do wierzchołka $v$ jest najkrótszą ścieżką w $G=(V,E)$ dla funkcji wagową $w$ wtedy i tylko wtedy, gdy jest najkrótszą ścieżką w $G$ dla funkcji wagowej $w_{h}$.

Dowód

Wniosek ten wynika wprost z Lematu 8 i Wniosku 9, który pokazuje, że odległości transformują się tak samo jak wagi ścieżek, a więc równość $w(p)=\delta (u,v)$ jest równoważna równości $w_{h}(p)=\delta _{h}(u,v)$.

Funkcję $h$ nazwiemy potencjałem jeżeli zachodzi:

$w_{h}(u,v)\geq 0,{\mbox{ dla }}(u,v)\in E.$      (4)

Pokażemy teraz, jak wyznaczyć funkcję potencjału $h$ dla grafu $G$. Rozważmy następujący algorytm:

Algorytm Algorytm obliczania potencjału

---

 OBLICZ-POTENCJAŁ$(G=(V,E),w)$
 1  $s$ nowy wierzchołek
 2  $V'=V\cup \{s\}$
 3  $E'=E\cup \{(s,v):v\in V\}$
 4  $w'(u,v)={\begin{cases}w(u,v),&{\mbox{jeżeli }}(u,v)\in E\\0&{\mbox{jeżeli }}u=s\\0&{\mbox{w pozostałych przypadkach}}\end{cases}}$
 5  $(d,\pi )=$BELLMAN-FORD$(G',w,s)$
 6  if $(d,\pi )=NIL$ then
 7    return $NIL$ (graf zawiera cykl ujemnej długości)
 8  return $d$ ($d(v)$ obliczone w algorytmie Bellmana-Forda jest potencjałem)

Działanie tego algorytmu przedstawione jest na poniższej animacji. <flash>file=Zasd_ilustr_c.swf |width=600|height=300</flash>

Lemat 11

Jeżeli graf $G=(V,E)$ z wagami krawędzi zadanymi funkcją $w$ zawiera cykl o ujemnej wadze, to algorytm OBLICZ-POTENCJAŁ zwraca wartość $NIL$. Natomiast w przeciwnym wypadku algorytm zwraca potencjał $d(v)$ dla grafu $G$ z funkcją wagową $w$.

Dowód

Zauważmy, że dodanie wierzchołka $s$ do grafu $G$ nie wprowadza nowych cykli, a jedynie powoduje, że wszystkie wierzchołki są osiągalne z $s$. Dlatego algorytm Bellmana-Forda uruchamiany dla $G'$ i wierzchołka $s$ zwraca $NIL$ wtedy i tylko wtedy, gdy $G$ zawiera cykl o ujemnej wadze.

Zakładamy teraz, że graf $G$ nie zawiera cyklu o ujemnej wadze, wtedy wartości $d(v)$ jako odległości w grafie spełniają:

$d(v)\leq d(u)+w(u,v).$

Innymi słowy:

$w_{d}(u,v)=w(u,v)+d(u)-d(v)\geq 0,$

co kończy dowód lematu.

Powyższy lemat jest ostatnim składnikiem potrzebnym nam do konstrukcji algorytmu Johnsona.

Algorytm Algorytm Johnsona

---

 JOHNSON$(G=(E,V),w)$
 1  $d=$OBLICZ-POTENCJAŁ$(G,w)$
 1  if $d=NIL$ then return $NIL$
 3  for każda krawędź $(u,v)\in E$ do
 4     $w_{d}(u,v)=w(u,v)+d(u)-d(v)$
 5  for każdy wierzchołek $u\in V$ do
 6    $(d_{h},\pi )$ = DIJKSTRA$(G,w_{h},u)$
 7    for każdy wierzchołek $v\in V$ do
 8      $d(u,v)=d_{h}(v)+h(v)-h(u)$
 9  return $D$

Poprawność tego algorytmu wynika wprost z Lematu 11. Czas działania algorytmu jest równy sumie czasu działania algorytmu Bellmana-Forda i czasu potrzebnego na $O(|V|)$ wywołań algorytmu Dijkstry, co daje całkowity czas $O(|V||E|+|V|^{2}\log |V|)$.