Informatyka MIMUW

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

//Inicjacja 
for v := 1 to n do 
begin 
  r[v] := 1; 
  w[v]:= \infty 
end; 
r[s] := 0; w[s] := 0; 
for each v \in L[s] do w[v] := w(v-s); 
//właściwe obliczenia 
for i := 1 to n-1 do 
begin
  u := MinR; 
  r[u] := 0 ; 
  for each v \in L[u] do if  r[v] = 1 then 
    if w[u] + w(u-v)  <  w[v]  then 
      w[v] := w[u] + w(u-v); 
end; 
//dla każdego v \in V, w[v] = w*(v) 

Dokonajmy analizy złożoności obliczeniowej tego algorytmu. Inicjacja, tak jak poprzednio, zajmuje czas \( O(n+m). \) Rozważmy teraz jeden obrót pętli for z wiersza 10. Niestety wiersz 12 nie uległ zmianie i tak jak poprzednio zajmuje czas \( \Theta(n) \). To powoduje, że cały algorytm działa w czasie \( \Theta(n^2) \). 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 \( O(m) \). Przyjrzyjmy się jakiego rodzaju operacje wykonujemy w naszym algorytmie. Nietrudno spostrzec, że kluczowe dla wydajności naszego algorytmu są operacje na zbiorze \( R \). Zbiór \( R \) jest zbiorem zmieniającym się dynamicznie podczas wykonywania algorytmu i składa się z wierzchołków grafu z przypisanymi im wagami. Na zbiorze \( R \) wykonywane są następujące operacje:

• \( MakeR \): zbuduj zbiór \( R \), 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 \( \infty \), gdy takie krawędzie nie istnieją - wiersze 1-7
• \( MinR \): znajdź w \( R \) wierzchołek o minimalnej wadze - wiersz 11
• \( DeleteMinR \): usuń z \( R \) znaleziony wierzchołek o minimalnej wadze - wiersz 12
• \( DecreaseKeyR(v,w') \): zmień wagę wierzchołka \( v \) na mniejszą wagę \( w' \) - 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:

• \( MakeR \) - \( O(n) \)
• \( MinR \) - \( O(1) \)
• \( DeleteMinR \) - \( O(\log n) \)
• \( DecreaseKeyR \) - \( O(\log n) \)

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 \( O(m\log n) \) i jest on asymptotycznie szybszy od algorytmu tablicowego dla każdego \( m \) rzędu mniejszego niż \( \frac{n^2}{\log n} \).

Kopiec Fibonacciego

Zauważmy, że operacją mającą decydujący wpływ na taką właśnie złożoność jest operacja zmniejszenia wagi \( DecreaseKeyR \). 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 \( DeleteMinR \) jest kosztem zamortyzowanym) jak w kopcu zwyczajnym. Zatem jeśli do implementacji zbioru \( R \) wykorzystamy kopiec Fibonacciego, czas działania metody Dijkstry wyniesie \( O(n\log n + m) \). Na praktyczne zachowanie się tego algorytmu duży wpływ ma jednak skomplikowana budowa kopców Fibonacciego.