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{array}{ll}0,& \text{jeśli }i=j,\\ \text{waga krawędzi }(i,j),& \text{jeśli }i\ne j\text{ i }(i,j)\in E,\\ \mathrm{\infty },& \text{jeśli }i\ne j\text{ i }(i,j)\ne E.\end{array}$

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 $\mathrm{\Pi }$. Macierz tą definiujemy używając funkcji ${\pi }_v$ w następujący sposób:

${\mathrm{\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}=\underset{k=1,\dots ,n}{\min }{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 ${\mathrm{\Pi }}_C$ i ${\mathrm{\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 ${\mathrm{\Pi }}_C$ ze ścieżkami ze zbioru ${\mathrm{\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$

Plik:Zasd ilustr f.svg

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 }(D+E)=C{\times }_{\min }D+C{\times }_{min}E$

oraz

$(D+E){\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{array}{ll}0,& \text{jeśli }i=j,\\ \mathrm{\infty },& \text{jeśli }i\ne j.\end{array}$

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}=\underset{k=1,\dots ,n}{\min }{\left(I_{\min }\right)}_{i,k}+C_{k,j}=$

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

$=\underset{k=i}{\min }{\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{array}{ll}{I}_{\min },& \text{jeżeli }m=0,\\ W{\times }_{\min }{W}^{m-1},& \text{jeżeli }m>0.\end{array}$

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{array}{ll}\min \{w(p):p\text{ ścieżka o długości }\le m\text{ z }u\text{ do }v\},& \text{jeżeli istnieje ścieżka o długości }\le m\text{ z }u\text{ do }v,\\ \mathrm{\infty }& \text{w przeciwnym przypadku.}\end{array}$

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 $\le 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)},\text{ dla }k\ge 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\ge 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}=\mathrm{\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,\dots ,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,\dots ,n\}$. Niech $d_{i,j}^{(k)}$ dla $k=0,\dots ,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,\dots ,k\}$. Pokażemy następujący rekurencyjny wzór na $D^{(k)}$.

Lemat 7

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

$d_{i,j}^{(k)}=\{\begin{array}{ll}{w}_{i,j},& \text{jeżeli }k=0,\\ \min (d_{i,j}^{(k-1)},d_{i,k}^{(k-1)}+d_{k,j}^{(k-1)}),& \text{jeżeli }k\ge 1.\end{array}$      (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,\dots ,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)\le 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)\le 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 {ℛ}$. Niech funkcja $h:V\to {ℛ}$ 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,\dots ,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}(w(v_i,v_{i+1})+h(v_i)-h(v_{i+1}))=$

$=\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)\ge 0,\text{ 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^{\prime }=V\cup \{s\}$
 3  $E^{\prime }=E\cup \{(s,v):v\in V\}$
 4  $w^{\prime }(u,v)=\{\begin{array}{ll}w(u,v),& \text{jeżeli }(u,v)\in E\\ 0& \text{jeżeli }u=s\\ 0& \text{w pozostałych przypadkach}\end{array}$
 5  $(d,\pi )=$BELLMAN-FORD$(G^{\prime },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.

Plik:Zasd ilustr c.svg

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^{\prime }$ 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)\le d(u)+w(u,v).$

Innymi słowy:

$w_d(u,v)=w(u,v)+d(u)-d(v)\ge 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|)$.