Algorytm Dijkstry

Rafał Nowak
rnowak

Problem najkrótszych ścieżek z jednym źródłem

Ponownie rozważmy problem znajdowania najkrótszych ścieżek w grafie.
Zaleca się zapoznanie najpierw z artykułem na temat algorytmu Bellmana-Forda.
Tym razem rozważamy graf skierowany $G=<V,E>$ z funkcją wagową $f:E\to R_+$.
Różnica jest taka, że tutaj funkcja wagowa jest nieujemna.
Rysunek

przedstawia przykład takiego grafu.
Wagi krawędzi oznaczono kolorem niebieskim. Warto myśleć, że liczby te reprezentują odległości pomiędzy wierzchołkami (wierzchołki mogą oznaczać np. miasta na mapie).

Przez długość ścieżki będziemy rozumieli sumę wag na jej krawędziach.
Rozważany problem polega więc na znalezieniu najkrótszych ścieżek wychodzących z jednego (wyróżnionego) wierzchołka (źródła) do wszystkich pozostałych.

Oczywiście, problem ten można rozwiązać wspomnianym już algorytmem Bellman Ford.
Okazuje się jednak, że warunek nieujemnych wag pozwala rozwiązać problem znacznie efektywniej.

Algorytm Dijkstry

Zanim przedstawimy algorytm, wprowadźmy pewne oznaczenia.
Niech $s$ oznacza wyróżniony wierzchołek (źródło), z którego chcemy wyznaczyć najkrótsze ścieżki.
Następnie, niech

$D[u]$ oznacza długość najkrótszej ścieżki ze źródła $s$ do wierzchołka $u$.

Najpierw zajmiemy się wyznaczeniem wartości $D[u]$ dla każdego wierzchołka $u\in V$.

Obserwacja 1

Skoro w grafie nie ma ujemnych wag, więc $D[s]=0$.

Możemy więc zaznaczyć ten fakt na rysunku

Wszystkie wierzchołki oprócz źródła mają początkowo wartość $D[u]=\infty$, gdyż nie wiemy jeszcze czy w ogóle istnieją do nich ścieżki od źródła. Niebieskim kolorem będziemy oznaczali wierzchołki, do których znamy najkrótsze odległości.
Wartości $D[u]$ przedstawiamy na rysunku w środku każdego wierzchołka. Skoro znamy już wartość $D[s]$, to możemy zaznaczyć ten wierzchołek kolorem niebieskim.

Zauważmy teraz, że mamy dwa zbiory wierzchołków: niebieskie i szare.
Zastanówmy się, co będzie jeśli niebieskie wierzchołki prześlą pewną informację do szarych wierzchołków. Mianowicie jeśli krawędź $u \to v$ jest krawędzią z niebieskiego wierzchołka $u$ do szarego wierzchołka $v$, to znaczy że można dość od źródła do wierzchołka $v$ ścieżką o długości $D[u] + f(u\to v)$. Czy jest to najkrótsza możliwa ścieżka? Niekoniecznie. Czasem tak. Zapamiętajmy więc tę informację w wierzchołku $v$. Na poniższym rysunku wartości te znajdują się w środku szarych wierzchołków

Ponieważ chcemy znać najkrótsze odległości do wszystkich wierzchołków, więc dążymy do tego wszystkie wierzchołki pomalować na niebiesko. Zastanówmy się, który z szarych wierzchołków mógłby teraz zmienić kolor na niebieski.
Zauważmy, że wszystkie szare wierzchołki mają pewną liczbę w środku (być może $\infty$).
Rozważmy szary wierzchołek $v$ z minimalną wartością w środku. Czy oznacza ona wartość $D[v]$$, czyli najkrótszą odległość od źródła. Okazuje się, że tak. Dowód tego faktu jest dość prosty. Wystarczy zauważyć, że wszystkie ścieżki od źródła do $v$ musiałyby przechodzić przez szare wierzchołki. Ponieważ ten ma minimalną wartość w środku oraz nie ma nigdzie indziej ujemnych wag, więc wartość ta jest długością najkrótszej ścieżki od źródła do wierzchołka $v$, a więc jest to prawidłowa wartość $D[v]$. W ten sposób otrzymujemy kolejny niebieski wierzchołek.
[[=D7_.png]]

Następnie postępujemy podobnie. *Nowy* niebieski wierzchołek wysyła informacje do swoich sąsiadów, tj. do wszystkich szarych, do których da się z niego dojść jedną krawędzią. Oni z kolei uaktualniają swoją przechowywaną wartość. W ten sposób sytuacja zmieni się następująco

Zauważmy, że szary wierzchołek na samej górze zmienił swoją wartość z $40$ na $25$. Oznaczmy go przez $w$. Czy jest to wartość $D[w]$. Niekoniecznie. Ponieważ są inne szare wierzchołki z mniejszą wartością, więc być może istnieje od nich krawędź z bardzo małą (nieujemną) wagą, a przez to być może znajdzie się krótsza droga od źródła do $w$.

W następnym kroku wybieramy więc wierzchołek z wartością $20$ i zmieniamy jego kolor

Ten z kolei poprawia wartości trzem szarym wierzchołkom

I tak dalej …
Na końcu otrzymujemy graf, w którym wszystkie wierzchołki są niebieskie i mają prawidłowe wartości $D[u]$.

Pseudokod: wyznaczanie wartości $D[u]$

Spróbujmy więc zapisać algorytm w pseudo języku.

1. Pomaluj wszystkie wierzchołki na kolor szary.
2. Dla wierzchołka startowego $s$ (źródła) nadaj wartość $D[s]:=0$, a wszystkim pozostałym wierzchołkom $u$ nadaj wartość $D[u] := \infty$
3. Dopóki istnieją szare wierzchołki
   1. Wybierz szary wierzchołek $u$ z minimalną wartością $D[u]$
   2. Zmień kolor wierzchołka $u$ na niebieski
   3. Dla wszystkich krawędzi $u\to v$, dla których $D[u]+f(u \to v) < D[v]$, wykonaj
      1. $D[v] := D[u]+f(u\to v)$

Powyższy algorytm oblicza wartości $D[u]$ oznaczające długość najkrótszych ścieżek od $s$ do $u$.
Aby móc odtworzyć te ścieżki wystarczy lekko zmodyfikować krok, w którym poprawiana jest wartość $D[v]$.
Mianowicie, w dodatkowej tablicy $\pi[v]$ będziemy przechowywali wierzchołek $u$, z którego przyszła najmniejsza wartość $D[u]+f(u\to v)$. Wówczas, w kroku 1.3.2, tzn. w momencie malowania wierzchołka $u$ na niebiesko, zapamiętana wartość $\pi[u]$ będzie wskazywała wierzchołek, z którego należy przyjść do $u$ chcąc dojść od źródła do $u$ w najkrótszy sposób.
Najkrótszą ścieżkę od $s$ do $u$ wyznaczymy więc w następujący sposób:

$u \leftarrow \pi[u] \leftarrow \pi[ \pi[u] ] \leftarrow \pi[ \pi[ \pi[u] ] ] \leftarrow \ldots \leftarrow s$.

Algorytm: animacja

Analiza złożoności

Niech $n$ oznacza liczbę wierzchołków w grafie, a $m$ —- liczbę jego krawędzi. Przypomnijmy, że jeśliby zastosować algorytm Bellmana-Forda do rozważanego tutaj problemu, to otrzymalibyśmy rozwiązanie o złożoności $O(n\cdot m)$, a więc $O(n^3)$. Podany powyżej pseudokod algorytmu Dijkstry można zrealizować w czasie $O( (n+m)\cdot \log n)$. Spróbujmy to uzasadnić. Zauważmy, że do realizacji algorytmu potrzebne są tablice $D[u]$, $\pi[u]$. Na zapamiętanie koloru każdego wierzchołka wystarczy także pewna tablica. Najtrudniejsze natomiast jest wykonanie kroku 3.1, w którym należy wybrać szary wierzchołek z minimalną wartością $D[u]$. Można to wykonać efektywnie, wystarczy pamiętać wszystkie szare wierzchołki w kolejce priorytetowej, gdzie priorytetem wierzchołka $u$ jest wartość $D[u]$. Wówczas wykonanie kroku 3.1 można zrealizować w czasie $O(1)$, a krok 3.2 polega na usunięciu szarego wierzchołka z kolejki priorytetowej, co zajmuje $O(n\log n)$. Krok 3.3 sumarycznie może zająć $O( m \log n )$. Łącznie otrzymujemy więc złożoność

$O( (n+m) \log n )$.