Algorytm Dijkstry

Algorytm Dijkstry

Ilustracja działania algorytmu
Rodzaj	Znajdowanie najkrótszej ścieżki
Struktura danych	graf
Złożoność
Czasowa	${\displaystyle O(E\cdot \log V)}$
Pamięciowa	${\displaystyle O(E+V\cdot \log V)}$ - przy użyciu kopca Fibonacciego

Algorytm Dijkstry, opracowany przez holenderskiego informatyka Edsgera Dijkstrę, służy do znajdowania najkrótszej ścieżki z pojedynczego źródła w grafie o nieujemnych wagach krawędzi.

Działanie

Mając dany graf z wyróżnionym wierzchołkiem (źródłem) algorytm znajduje odległości od źródła do wszystkich pozostałych wierzchołków. Łatwo zmodyfikować go tak, aby szukał wyłącznie (najkrótszej) ścieżki do jednego ustalonego wierzchołka, po prostu przerywając działanie w momencie dojścia do wierzchołka docelowego, bądź transponując tablicę incydencji grafu.

Algorytm Dijkstry znajduje w grafie wszystkie najkrótsze ścieżki pomiędzy wybranym wierzchołkiem a wszystkimi pozostałymi, przy okazji wyliczając również koszt przejścia każdej z tych ścieżek^[1].

Algorytm Dijkstry jest przykładem algorytmu zachłannego^[2].

Algorytm

Przez ${\displaystyle s}$ oznaczamy wierzchołek źródłowy, ${\displaystyle w(i,j)}$ to waga krawędzi ${\displaystyle (i,j)}$ w grafie.

• Stwórz tablicę ${\displaystyle d}$ odległości od źródła dla wszystkich wierzchołków grafu. Na początku ${\displaystyle d[s]=0,}$ zaś ${\displaystyle d[v]=\infty }$ dla wszystkich pozostałych wierzchołków.
• Utwórz kolejkę priorytetową ${\displaystyle Q}$ wszystkich wierzchołków grafu. Priorytetem kolejki jest aktualnie wyliczona odległość od wierzchołka źródłowego ${\displaystyle s.}$
• Dopóki kolejka nie jest pusta:
  • Usuń z kolejki wierzchołek ${\displaystyle u}$ o najniższym priorytecie (wierzchołek najbliższy źródła, który nie został jeszcze rozważony)
  • Dla każdego sąsiada ${\displaystyle v}$ wierzchołka ${\displaystyle u}$ dokonaj relaksacji poprzez ${\displaystyle u{:}}$ jeśli ${\displaystyle d[u]+w(u,v)<d[v]}$ (poprzez ${\displaystyle u}$ da się dojść do ${\displaystyle v}$ szybciej niż dotychczasową ścieżką), to ${\displaystyle d[v]:=d[u]+w(u,v).}$

Na końcu tablica ${\displaystyle d}$ zawiera najkrótsze odległości do wszystkich wierzchołków.

Dodatkowo możemy w tablicy poprzednik przechowywać dla każdego wierzchołka numer jego bezpośredniego poprzednika na najkrótszej ścieżce, co pozwoli na odtworzenie pełnej ścieżki od źródła do każdego wierzchołka – przy każdej relaksacji w ostatnim punkcie ${\displaystyle u}$ staje się poprzednikiem ${\displaystyle v.}$

Zastosowanie

Z algorytmu Dijkstry można skorzystać przy obliczaniu najkrótszej drogi do danej miejscowości. Wystarczy przyjąć, że każdy z punktów skrzyżowań dróg to jeden z wierzchołków grafu, a odległości między punktami to wagi krawędzi.

Jest często używany w sieciach komputerowych, np. przy trasowaniu (przykładowo w protokole OSPF).

Pseudokod

Dijkstra(G,w,s):
   dla każdego wierzchołka v w V[G] wykonaj
      d[v] := nieskończoność
      poprzednik[v] := niezdefiniowane
   d[s] := 0
   Q := V
   dopóki Q niepuste wykonaj
      u := Zdejmij_Min(Q)
      dla każdego wierzchołka v – sąsiada u wykonaj
         jeżeli d[v] > d[u] + w(u, v) to
            d[v] := d[u] + w(u, v)
            poprzednik[v] := u

   Wyświetl("Droga wynosi: " + d[v])

Dowód poprawności

Oznaczmy przez ${\displaystyle S}$ zbiór wierzchołków, które zostały już zdjęte z kolejki. Dowód opiera się na następujących dwóch faktach (niezmiennikach), prawdziwych przez cały czas trwania algorytmu:

1. Dla każdego wierzchołka ${\displaystyle v\in S,}$ liczba ${\displaystyle d[v]}$ jest długością najkrótszej ścieżki od ${\displaystyle s}$ do ${\displaystyle v.}$
2. Dla każdego wierzchołka ${\displaystyle v\notin S,}$ ${\displaystyle d[v]}$ jest długością najkrótszej ścieżki do ${\displaystyle v}$ prowadzącej tylko przez wierzchołki z ${\displaystyle S.}$

Na początku oba fakty są oczywiste (${\displaystyle S}$ jest zbiorem pustym). Przy zdejmowaniu wierzchołka ${\displaystyle u}$ z kolejki wiemy, na podstawie faktu 2, że nie da się do niego dojść żadną krótszą drogą przez wierzchołki z ${\displaystyle S.}$ Z drugiej strony, ponieważ ${\displaystyle u}$ ma najniższy priorytet, przejście przez jakikolwiek inny wierzchołek spoza ${\displaystyle S}$ dałoby od razu co najmniej tak samo długą ścieżkę. A zatem dołączając wierzchołek ${\displaystyle u}$ do ${\displaystyle S,}$ zachowujemy prawdziwość faktu 1. Następnie musimy uwzględnić fakt, że najkrótsza ścieżka do jakiegoś wierzchołka ${\displaystyle v}$ po wierzchołkach z nowego zbioru ${\displaystyle S}$ może teraz zawierać wierzchołek ${\displaystyle u.}$ Ale wtedy musi on być ostatnim na niej wierzchołkiem (do każdego innego dałoby się dojść krócej, nie używając ${\displaystyle u}$), a zatem jej długość równa jest ${\displaystyle d[u]+w(u,v)}$ i zostanie prawidłowo obliczona w następnym kroku algorytmu.

Złożoność

Złożoność obliczeniowa algorytmu Dijkstry zależy od liczby ${\displaystyle V}$ wierzchołków i ${\displaystyle E}$ krawędzi grafu. O rzędzie złożoności decyduje implementacja kolejki priorytetowej:

• wykorzystując „naiwną” implementację poprzez zwykłą tablicę, otrzymujemy algorytm o złożoności ${\displaystyle O(V^{2})}$
• w implementacji kolejki poprzez kopiec, złożoność wynosi ${\displaystyle O(E\log V)}$
• po zastąpieniu zwykłego kopca kopcem Fibonacciego złożoność zmienia się na ${\displaystyle O(E+V\log V)}$

Pierwszy wariant jest optymalny dla grafów gęstych (czyli jeśli ${\displaystyle E=\Theta (V^{2})}$), drugi jest szybszy dla grafów rzadkich ${\displaystyle (E=\Theta (V)),}$ trzeci jest bardzo rzadko używany ze względu na duży stopień skomplikowania i niewielki w porównaniu z nim zysk czasowy.

Problemy i algorytmy pokrewne

Algorytm Dijkstry nie działa, jeśli w grafie występują krawędzie z ujemnymi wagami – w tym wypadku używa się wolniejszego, lecz bardziej ogólnego algorytmu Bellmana-Forda. Jeśli graf nie jest ważony (wszystkie wagi mają wielkość 1), zamiast algorytmu Dijkstry wystarczy algorytm przeszukiwania grafu wszerz.

Algorytm A* jest pewnym uogólnieniem algorytmu Dijkstry, które pozwala przeszukiwać tylko część grafu, jednak wymaga dodatkowej wstępnej informacji (heurystyki) o odległościach wierzchołków.

Algorytm Prima znajdowania minimalnego drzewa rozpinającego oparty jest o bardzo podobny pomysł co algorytm Dijkstry.

Przypisy

Bibliografia

• E. W. Dijkstra: A note on two problems in connexion with graphs. In Numerische Mathematik, 1 (1959), S. 269–271.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford Wprowadzenie do algorytmów, wyd. 7, WNT 2007, ISBN 83-204-3149-2.

Linki zewnętrzne

• Algorytm Dijkstry na wazniak.mimuw.edu.pl
• Implementacja w języku C++
• Animacja algorytmu Dijkstry. optlab-server.sce.carleton.ca. [zarchiwizowane z tego adresu (2014-12-20)].
• Przykład wykonania algorytmu Dijkstry krok po kroku