Zaawansowane algorytmy i struktury danych/Wykład 6

From Studia Informatyczne

Spis treści

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



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. image:End_of_proof.gif

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. image:End_of_proof.gif


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}.
image:End_of_proof.gif

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 } \le m \mbox{ z } u \mbox{ do } v\}, & \mbox{jeżeli istnieje ścieżka o długości } \le 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 \le 1 krawędź. Korzystając teraz z Wniosku 1 otrzymujemy tezę dla m+1. image:End_of_proof.gif


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^{(k)}_{u,v}, \mbox{ 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. image:End_of_proof.gif

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 \ge 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) \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. image:End_of_proof.gif

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).
image:End_of_proof.gif


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). image:End_of_proof.gif


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

w_h(u,v) \ge 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.



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) \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. image:End_of_proof.gif


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