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{cases} 0, & jeśli i = j, \\ waga krawędzi (i, j), & jeśli i \neq j i (i, j) \in E, \\ \infty, & jeśli i \neq j 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 $δ (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 $π_{v}$ . Ponieważ tutaj interesuje nas wiele drzew to łatwiej będzie nam używać 'macierzy poprzedników $Π$ . Macierz tą definiujemy używając funkcji $π_{v}$ w następujący sposób:

Π_{v, u} = π_{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

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, \dots, n} C_{i, k} + D_{k, j} .$ (1)

Wniosek 1

Jeżeli założymy, że

C

i

D

opisują minimalne wagi odpowiednio zbioru ścieżek odpowiednio

Π_{C}

i

Π_{D}

w pewnym grafie

G

, to iloczyn odległości wyznacza minimalne wagi zbioru ścieżek powstałego z konkatenacji ścieżek ze zbioru

Π_{C}

ze ścieżkami zbioru

Π_{D}

.

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

Lemat 2

Dla macierzy

C

,

D

i

E

rozmiaru

n \times n

zachodzi:

(C \times_{\min} D) \times_{m i n} E = C \times_{\min} (D \times_{m i n} E) .

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_{m i n} E,

oraz

(D + E) \times_{\min} C = D \times_{\min} C + E \times_{m i n} 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:

{(I_{\min})}_{i, j} = {\begin{cases} 0, & jeśli i = j, \\ \infty, & 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

{(I_{\min} \times_{\min} C)}_{i, j} = \min_{k = 1, \dots, n} {(I_{\min})}_{i, k} + C_{k, j} =

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

= \min_{k = i} {(I_{\min})}_{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 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{cases} I_{\min}, & jeżeli m = 0, \\ W \times_{\min} W^{m - 1}, & 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 mniej 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ą mniej niż

m

krawędzi, tzn.:

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

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

\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 potrzebowali 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:

δ (u, v) = W_{u, v}^{(k)}, 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 \leq 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       $e_{i, j} = \infty$ 
 5      for  $k = 0$  to  $n - 1$  do
 6        e_{i,j} = \min(c_{i,k} + d_{k,j}, e_{i,j})
 7  return D'

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 obliczania odległości między wszystkimi parami wierzchołków I

 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 = 2 m$ 
 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 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 7

Dla

k = 0, \dots, n

zachodzi:

$d_{i, j}^{(k)} = {\begin{cases} w_{i, j}, & jeżeli k = 0, \\ \min (d_{i, j}^{(k - 1)}, d_{i, k}^{(k - 1)} + d_{k, j}^{(k - 1)}, & 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}, \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) \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ą to $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ą dodanie 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 ℛ$ . Funkcję $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 $δ (u, v)$ odległości w grafie $G$ dla funkcji wagowej $w$ oraz przez $δ_{h} (u, v)$ odległości w gafie $G$ dla funkcji wagowej $w_{h}$ .

Lemat 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 wniosek_9

Dla funkcji

w

,

w_{h}

, oraz dowolnej pary wierzchołków zachodzi:

δ_{h} (u, v) = δ (u, v) + h (u) - h (v) .

Wniosek lemat_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 wiec równość

w (p) = δ (u, v)

jest równoważna równości

w_{h} (p) = δ_{h} (u, v)

.

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

$w_{h} (u, v) \geq 0, dla < m a t h > (u, v) \in E$ . </math> (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), & jeżeli (u, v) \in E \\ 0, & jeżeli u = s \\ 0, w pozostałych przypadkach \end{cases}$ 
 5  if BELLMAN-FORD $(G^{'}, w, s) = F A L S E$  then
 6    return FALSE (graf zawiera cykl ujemnej długości)
 7  return TRUE ( $d (v)$  obliczone w algorytmie Bellmana-Forda jest potencjałem)

Lemat 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ść FALSE. Natomiast w przeciwnym wypadku algorytm zwraca TRUE i $d (v)$

potencjałem dla grafu

G

z funkcją wagową

w

.

Dowód

Zauważmy, że dodanie wierzchołka

s

do

grafu $G$ nie wprowadza nowych cykli do grafu, a jedynie powoduje, że wszystkie wierzchołki są osiągalne z $s$ . Dlatego algorytm Bellmana-Forda uruchomiany dla $G^{'}$ i wierzchołka $s$ zwraca TRUE wtedy i tylko wtedy gdy $G$ nie zawiera cyklu o ujemnej wadze.

Zakładamy teraz, że graf $G$ nie zawiera cykli 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  if OBLICZ-POTENCJAŁ $(G, w) = F A L S E$  then
 2    return FALSE
 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    wywołaj DIJKSTRA $(G, w_{h}, u)$  do policzenia odległości  $δ_{h} (u, v)$  dla    $v \in V$ 
 7    for każdy wierzchołek  $v \in V$  do
 8       $d (u, v) = d_{h} (u, v) + h (v) - h (u)$ 
 9  return  $D$

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

Zaawansowane algorytmy i struktury danych/Wykład 6

Spis treści

Abstrakt

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

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

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

Pomysł algorytmu

Algorytm

Algorytm Floyda-Warshalla

Algorytm Johnsona

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia