Tekst źródłowy strony Algorytmy i struktury danych/Algorytmy grafowe - najlżejsze ścieżki

Ten wykład poświęcimy wprowadzeniu do algorytmów grafowych. W tym celu rozwiążemy następujący problem ścieżkowy.

==Najlżejsze ścieżki z jednym źródłem==

W tym wykładzie pisząc graf będziemy mieli zawsze na uwadze graf spójny i nieskierowany. Tradycyjnie przez <math>n</math> będziemy oznaczali liczbę wierzchołków w grafie, a przez <math>m</math> liczbę jego krawędzi. Dla każdego grafu mamy zawsze <math>n-1 \le m \le n(n-1)/2</math>.

Niech <math>G=(V,E)</math> będzie grafem, a  <math>w: E \rightarrow \{1,2,...\}</math> funkcją przypisująca krawędziom dodatnie liczby całkowite zwane wagami krawędzi. Krawędzie <math>(u,w)\in E</math> będziemy oznaczali przez <math>u-w</math>.

Ciąg wierzchołków <math>p=< v_0, v_1,\ldots , v_k ></math> nazywamy ścieżką w <math>G</math> wtedy i tylko wtedy, gdy <math>v_i - v_{i+1}</math> jest krawędzią w <math>E</math>, dla każdego <math>i = 0, 1,\ldots,k-1</math>. Liczbę <math>k</math> nazywamy długością ścieżki <math>p</math>.

Wagą ścieżki <math>p</math> nazywamy sumę wag jej krawędzi i oznaczamy także przez <math>w(p)</math>. Przyjmujemy, że waga ścieżki o długości 0 wynosi 0.

Przez <math>N(v)</math> będziemy oznaczali zbiór sąsiadów wierzchołka <math>v</math> w grafie <math>G</math>.

Problem (wag) najlżejszych ścieżek z jednym źródłem definiuje się następująco
(uwaga: w literaturze przyjęło się też wagę ścieżki nazywać długością i dlatego często mówi się o problemie najkrótszych ścieżek).

----

'''Dane:'''

<math>G=(V,E)</math> – spójny, nieskierowany graf

<math>w: E\rightarrow \{1,2,\ldots\}</math> – funkcja przypisująca krawędziom   dodatnie liczby całkowite 

<math>s</math> – wyróżniony wierzchołek w G, zwany źródłem

'''Wynik:'''

dla każdego wierzchołka <math>v</math>, waga <math>w^*(v)</math> najlżejszej ścieżki łączącej <math>v</math> z <math>s</math>.

----

Na tym wykładzie zajmiemy się tylko wyznaczaniem wag najlżejszych ścieżek. Znalezienie sposobu wyznaczania takich ścieżek pozostawiamy jako ćwiczenie dla czytelnika. Problem najlżejszych scieżek jest problemem bardzo naturalnym. Jeśli mapę drogową potraktować jako graf, w którym wagi to długości odcinków drogowych na mapie, a źródło jest wyróżnionym miastem na mapie  (na przykład stolicą państwa), to rozwiązanie problemu najlżejszych ścieżek da nam długości najkrótszych dróg od miasta-źródła do pozostałych miast na mapie.

Znaczenie problemu najlżejszych ścieżek jest dużo większe niż by to wynikało z jego zastosowań. Poszukując wydajnego algorytmu dla rozwiązania tego problemu, postaramy się przedstawić cały proces projektowania, a następnie implementowania algorytmu ze szczególnym uwzględnieniem doboru odpowiednich struktur danych w celu osiągnięcia lepszej wydajności implementacji.

Nasze rozważania rozpoczniemy od schematu algorytmu poszukiwania najlżejszych ścieżek, a następnie zajmiemy się implementacją poszczególnych elementów tego schematu. Rozwiązanie, które zaproponujemy pochodzi od wybitnego holenderskiego informatyka Edgara Dijkstry.

Zastanówmy się, w jaki sposób obliczać wagi najlżejszych ścieżek. Pomoże nam w tym następujące proste spostrzeżenie:

----

Niech <math><v=v_0,v_1,\ldots,v_k=s></math> będzie najlżejszą ścieżką z wierzchołka <math>v</math> do źródła <math>s</math>. Wówczas <math>w^*(v) > w^*(v_1)>\ldots > w^*(v_k)=0</math>.

----

Spostrzeżenie to mówi, że gdybyśmy obliczali wagi najlżejszych ścieżek od najlżejszej do najcięższej, to dla każdego wierzchołka <math>v</math> różnego od źródła, sąsiad <math>v</math> na najlżejszej ścieżce z <math>v</math> do <math>s</math> miałby swoją wagę już obliczoną i tym sąsiadem byłby wierzchołek (może być więcej niż jeden wybór), dla którego waga najlżejszej ścieżki do <math>s</math>, powiększona o wagę krawędzi łączącej go z <math>v</math>, jest najmniejsza.

Możemy teraz przystąpić do schematu algorytmu. Algorytm obliczania najlżejszych ścieżek będzie działał w <math>n-1</math> fazach. W trakcie działania algorytmu <math>L</math> będzie zbiorem tych wierzchołków, dla których wagi najlżejszych scieżek prowadzące do <math>s</math> zostały już obliczone. Przez <math>R</math> będziemy oznaczali zbiór pozostałych wierzchołków. Podczas obliczeń z każdym wierzchołkiem <math>v</math> będziemy mieli związana nieujemną wagę <math>w[v]</math>. Dla każdego wierzchołka <math>v \in L</math> waga <math>w[v]</math> będzie wagą najlżejszej scieżki łączacej <math>v</math> z <math>s</math>, czyli <math>w[v] = w^*(v)</math>. Dla każdego wierzchołka <math>v</math> z <math>R</math>, <math>w[v]</math> będzie równe wadze najlżejszej ścieżki z <math>v</math> do <math>s</math>, na której wszystkie wierzchołki poza <math>v</math> należą do <math>L</math>. Może się zdarzyć, że taka ścieżka nie istnieje. Wówczas przyjmujemy, że <math>w[v]</math> jest równe <math>\infty</math> - umownej wartości większej od wszystkich wag występujących w obliczeniach. Jedna faza algorytmu będzie polegała na przeniesieniu do <math>L</math> wierzchołka z <math>R</math> o najmniejszej wadze <math>w</math>, a następnie poprawieniu wag <math>w</math> dla wierzchołków, które pozostały w <math>R</math>. Zauważmy, że wagi <math>w</math> mogą się zmienić tylko sąsiadom wierzchołka przeniesionego do <math>L</math>, którzy pozostali w <math>R</math>. Oto schemat algorytmu obliczania najlżejszych ścieżek. Nazwiemy go metodą Dijkstry.

{{algorytm|Metoda Dijkstry|algorytm_dijkstry|
  1  //Inicjacja
  2  <math>L := \{s\}</math>; <math>R := V-\{s\}</math>;
  3  <math>w[s] := 0</math>; 
  4  '''for each''' <math>v \in R</math> '''do'''
  5    '''if''' <math>v-s \in E</math> '''then'''
  6      <math>w[v] := w(v-s)</math>
  7    '''else'''
  8      <math>w[v] := \infty</math>;
  9  //właściwe obliczenia
  10 '''for''' <math>i := 1</math> '''to''' <math>n-1</math> '''do''' 
  11 '''begin'''
  12   <math>u :=</math> wierzchołek z <math>R</math> o minimalnej wadze <math>w[u]</math>;
  13   <math>R := R - \{u\}</math>; 
  14   <math>L := L + \{u\}</math>;
  15   '''for each''' <math>v \in N(u)\cap R</math> '''do'''
  16     '''if''' <math>w[u] + w(u-v) < w[v]</math> '''then'''
  17       <math>w[v] := w[u] + w(u-v)</math>;
  18 '''end''';
  20 //dla każdego <math>v \in V</math>, <math>w[v] = w^*(v)</math>
}}

Dlaczego powyższy opis obliczania wag najlżejszych ścieżek nazwaliśmy metodą Dijkstry, a nie algorytmem Dijkstry? Zauważmy, że żeby powyższą metodę móc zaimplementować na komputerze, a także dokonać analizy jej złożoności obliczeniowej, musimy doprecyzować wiele elementów schematu. Należą do nich

* implementacja grafu;
* implementacje zbiorów <math>L</math> i <math>P</math> oraz operacji na nich (inicjacja, usuwanie i dodawanie wierzchołka, znajdowanie wierzchołka o minimalnej wadze, zmiana wagi wierzchołka).

Dopiero ścisłe określenie tych elementów da nam pełną implementację metody, a tym samym algorytm, który będzie mógł być poddany analizie.

Zaczniemy od implementacji, w której wszystkie struktury danych są tablicami. Zanim to jednak zrobimy, zastanówmy się, w jaki sposób wygodnie zadać graf jako daną dla algorytmu. Zawyczaj przyjmuje się, że wierzchołki grafu utożsamiamy z liczbami naturalnymi <math>1,2,\ldots, n</math>, natomiast krawędzie opisujemy jako pary liczb odpowiadające końcom krawędzi. Gdy dodatkowo, tak jak w problemie najlżejszych ścieżek, z każdą krawędzią związana jest waga, to z każdą parą liczb opisującą końce krawędzi podajemy trzecią liczbę - wagę tej krawędzi. Tak więc graf możemy zadać w następujący sposób:

* wiersz pierwszy: para liczb ''n'', ''m'' - odpowiednio liczba wierzchołków i krawędzi grafu
* ''m'' wierszy, z których każdy zawiera parę (trójkę) liczb reprezentujących końce jednej krawędzi (i jej wagę).

Zauważmy, że jeśli graf jest spójny, jego rozmiar wynosi <math>O(m)</math>, gdzie <math>n-1 < m \le \frac{n(n-1)}{2}</math>.

Taki sposób reprezentacji grafu nie jest wygodny w obliczeniach, ponieważ nie daje on prawie żadnej informacji o strukturze grafu. Dlatego w algorytmach grafowych przyjmuje się, że graf jest implementowany na jeden z dwóch sposobów.

==Macierz sąsiedztwa==
 
W implementacji tablicowej zakłada się, że graf jest reprezentowany przez tak zwaną '''macierz sąsiedztwa'''. W najczystszej postaci macierz sąsiedztwa jest macierzą kwadratową indeksowaną wierzchołkami grafu, której elementy przyjmują wartości 0 lub 1. Jedynka (1) na przecięciu <math>i</math>-tego wiersza i  <math>j</math>-tej kolumny mówi, że w grafie jest krawędź o końcach w <math>i</math> oraz <math>j</math>, zaś zero (0) oznacza, że takiej krawędzi nie ma. W przypadku, gdy krawędzie mają wagi, macierz sąsiedztwa można zmodyfikować w następujący sposób. Jeśli <math>i-j</math> jest krawędzią w grafie, to na przecięciu tej <math>i</math>-tego wiersza i <math>j</math>-tej kolumny wstawiamy wagę <math>w(i-j)</math>. Gdy takiej krawędzi nie ma w grafie, to w to miejsce wstawiamy <math>\infty</math>. W takim przypadku elementy macierzy traktujemy jako wagi bezpośrednich połączeń pomiędzy wierzchołkami w grafie. Żeby być w zgodzie z tą konwencją przyjmujemy, że na przekątnej macierzy sąsiedztwa zawsze stawiamy zera. Podsumowując, w implementacji tablicowej przyjmujemy, że graf jest reprezentowany przez macierz kwadratową <math>A[1..n,1..n]</math> taką,że
<center>
<math>
A[i,j] = \left\{\begin{array}{ll}
  w(i-j) & i-j \in E\\
\infty & i-j \not \in E \mbox{ oraz } i \ne j\\
0 & i = j
\end{array}
\right.</math>
</center>

Głównymi zaletami tej reprezentacji są jej prostota i to, że łatwo sprawdzać w czasie stałym, czy dwa wierzchołki są połączone krawędzią w grafie. Wadą jest to, że niezależnie od rozmiaru grafu, rozmiar tej reprezentacji jest zawsze kwadratowy. Tyle też czasu zajmuje jej inicjacja. Nawet jeśli byśmy przyjęli, że taka reprezentacja jest z góry zadana, to okazuje się, że przy tej reprezentacji grafu algorytmy dla znakomitej większości naturalnych problemów grafowych działają w czasie <math>\Omega(n^2)</math>. Nie jest to źle dla grafów gęstych, w których <math>m=\Theta(n^2)</math>, ale gdy chcemy uzyskiwać szybsze algorytmy dla grafów rzadszych, w szczególności liniowe ze względu na rozmiar grafu, to musimy myśleć o innej ich reprezentacji. Taką reprezentacją jest reprezentacja listowa.

==Listy sąsiedztw==

W tej implementacji dla każdego wierzchołka w grafie pamiętamy listę jego sąsiadów zwaną listą sąsiedztwa. Innymi słowy, graf jest pamiętany w tablicy list <math>L[1..n]</math>, gdzie <math>L[i]</math> jest listą sasiedztwa wierzchołka <math>i</math>. W przypadku grafu z wagami, jeśli wierzchołek <math>j</math> występuje na liście wierzchołka <math>i</math>, to z wystąpieniem wierzchołka <math>j</math> związana jest waga krawędzi <math>i-j</math>. Kolejność wierzchołków na liście może być dowolna. Zauważmy, że suma długości list sąsiedztw wynosi <math>2m</math>, a zatem rozmiar struktury danych reprezentującej graf wynosi <math>O(n+m)</math> i jest on liniowy ze względu na rozmiar danych. Listy <math>L</math> można łatwo zbudować w czasie liniowym. Jeśli więc chcemy uzyskiwać algorytmy, których złożoności jak najlepiej zależą od rozmiaru grafu, a w szczególności są liniowe ze względu na ten rozmiar, należy reprezentować graf przez '''listy sąsiedztw'''.

Możemy teraz powrócić do problemu najlżejszych ścieżek i zająć się implementacją schematu Dijkstry.

==Implementacja tablicowa==

W tej implementacji wszystkie struktury danych są tablicami. Przyjmujemy, że graf jest zadany przez macierz sąsiedztwa <math>A[1..n,1..n]</math>. Zbiór <math>R</math> jest rerezentowany za pomocą  tablicy (wektora charakterystycznego) <math>r[1,\ldots,n]</math> o wartościach 0-1:
<center>
<math>
r[i] = \left\{ \begin{array}{ll}
  1 & i \in R\\
  0 & i \in L = V-R
\end{array}
\right. 
</math>
</center>
Tablica <math>w[1..n]</math> służy do obliczania wag najlżejszych ścieżek.
Oznaczmy przez <math>MinR</math> funkcję, której wartością jest wierzchołek w ''R'' o najmniejszej wadze <math>w</math>. Jeśli jest więcej niż jeden taki wierzchołek, to wynikiem funkcji może być dowolny z nich. Oto jedna z możliwych implementacji tej funkcji.

 1  '''function''' <math>MinR</math>;
 2  '''begin'''
 3    <math>min := 0</math>;
 4    '''for''' <math>i := 1</math> '''to''' <math>n</math> '''do'''  
 5      '''if''' <math>w[i] < min</math> '''then''' <math>min\_v := i</math>; 
 6    return <math>min\_v</math>
 7  '''end'''

Czas działania tej funkcji wynosi <math>O(n)</math>.

Możemy teraz przedstawić pierwszą implementację metody Dijkstry.

{{algorytm|Metoda Dijkstry - implementacja tablicowa||
  1  //Inicjacja
  2  '''for''' <math>v := 1</math> '''to''' <math>n</math> '''do'''  
  3  '''begin''' 
  4    <math>r[v] := 1</math>;
  5    <math>w[v] := A[v,s]</math>
  6  '''end''';
  7  <math>r[s] := 0</math>;
  8  
  9  //właściwe obliczenia
  10 '''for''' <math>i := 1</math> '''to''' <math>n-1</math> '''do''' 
  11 '''begin'''
  12   <math>u := MinR</math>;
  13   <math>r[u] := 0</math>; 
  14   
  15   '''for''' <math>v := 1</math> '''to''' <math>n</math> '''do''' '''if''' <math>r[v] = 1</math> '''then'''
  16     '''if''' <math>w[u] + A[u,v] < w[v]</math> '''then'''
  17       <math>w[v] := w[u] + A[u,v]</math>
  18 '''end''';
  20 //dla każdego <math>v \in V</math>, <math>w[v] = w^*(v)</math>
}}

W powyższej implementacji grupy wierszy 2-8, 12-14 oraz 15-18 odpowiadają dokładnie tym samym grupom wierszy w opisie metody Dijkstry. Analiza złożoności czasowej powyższego algorytmu nie nastręcza żadnych trudności. Inicjacja zajmuje czas <math>O(n)</math>, każdy obrót pętli '''for''' z wiersza 10 zajmuje także czas <math>O(n)</math>, a zatem cały algorytm działa w czasie <math>\Theta(n^2)</math>. Dla grafów gęstych, czyli zawierających rzędu <math>n^2</math> wierzchołków, jest to algorytm optymalny. Zwróćmy także uwagę na jego wyjątkowo prosty i elegancki zapis. Co jednak, gdy zadany graf nie jest grafem gęstym? Czy wówczas możemy obliczać wagi najlżejszych ścieżek szybciej?

==Implementacja listowa==

Pierwszym krokiem, jaki podejmiemy, jest przyjęcie reprezentacji grafu przez listy sąsiedztw. Załóżmy, że jest to jedyna zmiana w implementacji. Oto zapis metody Dijsktry przy tej zmianie.

{{algorytm|Metoda Dijkstry - implementacja listowa||
  1  //Inicjacja
  2  '''for''' <math>v := 1</math> '''to''' <math>n</math> '''do'''  
  3  '''begin'''
  4    <math>r[v] := 1</math>;
  5    <math>w[v] := \infty</math>
  6  '''end''';
  7  <math>r[s] := 0; w[s] := 0</math>;
  8  '''for each''' <math>v \in L[s]</math> '''do''' <math>w[v] := w(v-s)</math>;
  9  //właściwe obliczenia
  10 '''for''' <math>i := 1</math> '''to''' <math>n-1</math> '''do''' 
  11 '''begin'''
  12   <math>u := MinR</math>;
  13   <math>r[u] := 0</math>; 
  14   
  15   '''for each''' <math>v \in L[u]</math> '''do''' '''if''' <math>r[v] = 1</math> '''then'''
  16     '''if''' <math>w[u] + w(u-v) < w[v]</math> '''then'''
  17       <math>w[v] := w[u] + w(u-v)</math>;
  18 '''end''';
  20 //dla każdego <math>v \in V</math>, <math>w[v] = w^*(v)</math>
}}

Dokonajmy analizy złożoności obliczeniowej tego algorytmu. Inicjacja, tak jak poprzednio, zajmuje czas <math>O(n+m)</math>. Rozważmy teraz jeden obrót pętli '''for''' z wiersza 10. Niestety wiersz 12 nie uległ zmianie i tak jak poprzednio zajmuje czas <math>\Theta(n)</math>. To powoduje, że cały algorytm działa w czasie <math>\Theta(n^2)</math>. Mamy jednak pewien zysk w wierszach 15-17. Zauważmy, że w tych wierszach, dla każdego wierzchołka różnego od źródła przeglądamy dokładnie raz jego listę sąsiedztwa, a obsługa jednego wierzchołka na liście zajmuje stały czas. Tak więc łączny koszt wykonania pętli '''for''' z wiersza 15 wynosi <math>O(m)</math>. Przyjrzyjmy się jakiego rodzaju operacje wykonujemy w naszym algorytmie. Nietrudno spostrzec, że kluczowe dla wydajności naszego algorytmu są operacje na zbiorze <math>R</math>. Zbiór <math>R</math> jest zbiorem zmieniającym się dynamicznie podczas wykonywania algorytmu i składa się z wierzchołków grafu z przypisanymi im wagami. Na zbiorze <math>R</math> wykonywane są następujące operacje:

* <math>MakeR</math>: zbuduj zbiór <math>R</math>, na który składają się wszystkie wierzchołki poza źródłem i których wagami są wagi krawędzi łączące je ze źródłem lub <math>\infty</math>, gdy takie krawędzie nie istnieją - wiersze 1-7
* <math>MinR</math>: znajdź w <math>R</math> wierzchołek o minimalnej wadze - wiersz 11
* <math>DeleteMinR</math>: usuń z <math>R</math> znaleziony wierzchołek o minimalnej wadze - wiersz 12
* <math>DecreaseKeyR(v,w')</math>: zmień wagę wierzchołka <math>v</math> na mniejszą wagę <math>w'</math> - wiersz 17

Powyższe operacje są operacjami kolejki priorytetowej. Powstaje pytanie, którą z licznych implementacji kolejki priorytetowej tu wykorzystać. Skupimy się na dwóch implementacjach.

'''Kopiec zwyczajny'''

W tej implementacji zbiór reprezentujemy za pomocą kopca zwyczajnego, o którym była mowa przy okazji sortowania kopcowego. Koszty wykonania poszczególnych operacji wynoszą w tym przypadku:

* <math>MakeR</math> - <math>O(n)</math>
* <math>MinR</math> - <math>O(1)</math>
* <math>DeleteMinR</math> - <math>O(\log n)</math>
* <math>DecreaseKeyR</math> - <math>O(\log n)</math>

Szczegóły implementacyjne metody Dijkstry z wykorzystaniem kopca zwyczajnego zostawiamy jako zadanie dla Czytelnika. Tak zaimplementowany algorytm obliczania najlżejszych ścieżek działa w czasie <math>O(m\log n)</math> i jest on asymptotycznie szybszy od algorytmu tablicowego dla każdego <math>m</math> rzędu mniejszego niż <math>\frac{n^2}{\log n}</math>. 

'''Kopiec Fibonacciego'''

Zauważmy, że operacją mającą decydujący wpływ na taką właśnie złożoność jest operacja zmniejszenia wagi <math>DecreaseKeyR</math>. Wiemy jednak, że w kopcach Fibonacciego zamortyzowany koszt tej operacji jest stały. To jest wystarczające do naszych celów, tym bardziej, że koszty pozostałych operacji są takie same (koszt <math>DeleteMinR</math> jest kosztem zamortyzowanym) jak w kopcu zwyczajnym. Zatem jeśli do implementacji zbioru <math>R</math> wykorzystamy kopiec Fibonacciego, czas działania metody Dijkstry wyniesie <math>O(n\log n + m)</math>. Na praktyczne zachowanie się tego algorytmu duży wpływ ma jednak skomplikowana budowa kopców Fibonacciego.