Zaawansowane algorytmy i struktury danych/Wykład 6

Abstrakt

W wykładzie tym zajmiemy się problemem obliczanie odległości w grafie między wszystkimi parami wierzchołków w grafie ważonym skierowanym $G=(V,E)$. Przedstawimy trzy algorytmu 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 implementacji 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 to ł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$. Jak to zostało pokazane w Zadaniu 3 do poprzedniego wykładu znając odległości w grafie drzewo najkrótszych ścieżek można wyznaczyć w czasie $O(|E|)$, a 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 4 do Wykładu 4.

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

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 wniosek_konkatenacja

Jeżeli założymy, że $C$ i $D$ opisują minimalne wagi odpowiednio 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 zbioru ${\mathrm{\Pi }}_D$.

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

Lemat io_łączny

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 io_przemienny

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 io_jedynka

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$, to 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}.$

Łączność iloczynu odległości ma dla nas bardzo ważne konsekwencję 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(n^3\log n)$. 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 mniej niż $m$ krawędzi.

Lemat potęgi_odległości

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ą mniej 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$. Dla danego wierzchołka istnieją dla niech tylko ścieżki długości zero prowadzące do niego samego, 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 ze definicji 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 potrzebowali jeszcze udowodnić następujące dwa lematy.

Lemat 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\le n-1$.

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 algorytm_iloczyn_odległości

---

 {{{3}}}

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

Algorytm algorytm_apsp_mnozenie

---

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

Poprawności 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 {{kotwica|wierzchołek_wewnetrzny|wewnetrznym} ś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 $\{v_1,\dots ,v_k$. Pokażemy następujący rekurencyjny wzór na $D^{(k)}$.

Lemat 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}$

Dowód

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

{{{3}}}      (2

$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ą to $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

---

 między wszystkimi parami wierzchołków I
 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)}$