Zaawansowane algorytmy i struktury danych/Wykład 6

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 . Przedstawimy trzy algorytmy rozwiązujące ten problem:

  • algorytm wykorzystujący mnożenie macierzy, działający w czasie ,
  • algorytm Floyda-Warshalla, działający w czasie ,
  • algorytm Johnsona, działający w czasie .

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 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 , co daje nam algorytm rozwiązujący problem policzenia odległości między wszystkimi parami wierzchołków, działający w czasie .

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 . 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 rozmiaru reprezentującą wagi krawędzi -wierzchołkowego grafu . Dla macierzy tej zachodzi:



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



W pozostałej części tego wykładu zajmiemy się tylko wyznaczaniem macierzy odległości . 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 . Tak więc drzew możemy wyliczyć w czasie . 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 .


Co więcej, będziemy zakładać, że w grafie nie ma ujemnych cykli. Ujemne cykle można wykryć w czasie 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 oraz rozmiaru . Dla macierzy tych definiujemy operację iloczyn odległości, której wynikiem jest także macierz rozmiaru , zdefiniowana jako:

     (1)


Wniosek 1

Jeżeli założymy, że i opisują minimalne wagi zbioru ścieżek odpowiednio i w pewnym grafie , to iloczyn odległości wyznacza minimalne wagi zbioru ścieżek powstałego z konkatenacji ścieżek ze zbioru ze ścieżkami ze zbioru .

Wniosek ten jest przedstawiony na poniższej animicji, gdzie zostały zaznaczone dwa zbiory ścieżek, pierwszy, zaznaczony na zielono, reprezentowany przez macierz oraz graf , oraz drugi, zaznaczony na niebiesko, reprezentowany przez macierz oraz graf . W wyniku wykonania mnożenia otrzymujemy macierz oraz graf

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

Lemat 2

Dla macierzy , i rozmiaru zachodzi:

Dowód

Powyższa równość wynika wprost z wzoru (1) oraz przemienności operacji . End of proof.gif

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

Lemat 3

Dla macierzy , i rozmiaru zachodzi:



oraz


Dowód

Te dwie równości wynikają ponownie z wzoru (1) oraz przemienności operacji względem dodawania. End of proof.gif


Zdefiniujmy macierz rozmiaru jako:



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


Lemat 4

Dla macierzy rozmiaru zachodzi:


Dowód

Mamy

ponieważ wszystkie elementy równe są oprócz elementu , możemy je pominąć w operacji i:


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 . Niech będzie macierzą wag grafu . Rozważmy macierz zdefiniowaną jako:


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

Lemat 5

Element macierzy zadaje najmniejszą wagę ścieżki, wychodzącej z wierzchołka do wierzchołka spośród ścieżek, które zawierają nie więcej niż krawędzi, tzn.:


Dowód

Tezę tę udowodnimy przez indukcję po . Ścieżki używające krawędzi istnieją tylko z każdego wierzchołka do niego samego i mają długość , a więc dla teza wynika wprost z definicji macierzy . Załóżmy teraz, że teza zachodzi dla . Mamy wtedy . Zauważmy, że definicja macierzy wag opisuje ścieżki używające krawędź. Korzystając teraz z Wniosku 1 otrzymujemy tezę dla . 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 , w którym wagi krawędzi zadane są macierzą nie istnieje cykl o ujemnej wadze to:


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 . Z Lematu 5 wynika więc, że odległości tych ścieżek są dobrze wyznaczone w dla . End of proof.gif

Algorytm

Zauważmy, że iloczyn odległości dwóch macierzy możemy policzyć w czasie wykorzystując następujący algorytm.


Algorytm Mnożenia macierzy odległości


 MNOŻENIE-ODLEGŁOŚCI
 1   macierz rozmiaru 
 2  for  to  do
 3    for  to  do
 4    begin
 5      
 6      for  to  do
 7        
 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
 1  
 2  
 3  while  do
 4  begin
 5    MNOŻENIE-ODLEGŁOŚCI
 6    
 7  end
 8  return 

Poprawność tego algorytmu wynika wprost z Lematu 6 ponieważ na zakończenie algorytmu i .

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 jest każdy wierzchołek na ścieżce różny od jej początku i końca .

Niech zbiorem wierzchołków grafu będzie . Niech dla oznacza najmniejszą wagę ścieżki z do spośród ścieżek, których wierzchołki wewnętrzne należą do zbioru . Pokażemy następujący rekurencyjny wzór na .

Lemat 7

Dla zachodzi:

     (2)

Dowód

Dla poprawność powyższego wzoru wynika bezpośrednio z definicji . Dla musimy pokazać, że



Niech będzie najkrótszą ścieżką z do , której wierzchołki wewnętrzne należą do zbioru . Mamy dwa przypadki:

  • Wierzchołek nie leży na ścieżce . Wtedy zachodzi . Ponieważ jest najkrótszą ścieżką, to także i powyższy wzór zachodzi.
  • Jeżeli wierzchołek należy do ścieżki , to występuje on dokładnie raz i możemy podzielić na dwie ścieżki z do oraz z do . Ścieżki i nie zawierają wierzchołka 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 oraz . Otrzymujemy więc . Ponieważ jest najkrótszą ścieżką, i wzór zachodzi także w tym przypadku. End of proof.gif

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

Algorytm Algorytm Floyda-Warshalla


 ODLEGŁÓŚCI-II
 1  ,
 2  for  to  do
 3    for  to  do
 4      for  to  do
 5        
 6  return 


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 . 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 wraz z funkcją wagową . Niech funkcja będzie dowolną funkcją ze zbioru wierzchołków w liczby rzeczywiste. Dla funkcji oraz definiujmy nową funkcję wagową oznaczoną w następujący sposób:

     (3)

Oznaczmy, przez odległości w grafie dla funkcji wagowej oraz przez odległości w grafie dla funkcji wagowej .

Lemat 8

Dla funkcji , oraz dowolnej ścieżki zachodzi:

Dowód

Mamy:


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 , , oraz dowolnej pary wierzchołków zachodzi:


Wniosek 10

Ścieżka z wierzchołka do wierzchołka jest najkrótszą ścieżką w dla funkcji wagową wtedy i tylko wtedy, gdy jest najkrótszą ścieżką w dla funkcji wagowej .

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ść jest równoważna równości . End of proof.gif


Funkcję nazwiemy potencjałem jeżeli zachodzi:

     (4)


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

Algorytm Algorytm obliczania potencjału


 OBLICZ-POTENCJAŁ
 1   nowy wierzchołek
 2  
 3  
 4  
 5  BELLMAN-FORD
 6  if  then
 7    return  (graf zawiera cykl ujemnej długości)
 8  return  ( obliczone w algorytmie Bellmana-Forda jest potencjałem)

Działanie tego algorytmu przedstawione jest na poniższej animacji.

Lemat 11

Jeżeli graf z wagami krawędzi zadanymi funkcją zawiera cykl o ujemnej wadze, to algorytm OBLICZ-POTENCJAŁ zwraca wartość . Natomiast w przeciwnym wypadku algorytm zwraca potencjał dla grafu z funkcją wagową .

Dowód

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

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



Innymi słowy:



co kończy dowód lematu. End of proof.gif


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

Algorytm Algorytm Johnsona


 JOHNSON
 1  OBLICZ-POTENCJAŁ
 1  if  then return 
 3  for każda krawędź  do
 4     
 5  for każdy wierzchołek  do
 6     = DIJKSTRA
 7    for każdy wierzchołek  do
 8      
 9  return 

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 wywołań algorytmu Dijkstry, co daje całkowity czas .