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

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia graf drzewo podgraf cykl klika stopień wierzchołka stopień grafu dopełnienie grafu obwód grafu pokrycie wierzchołkowe liczba chromatyczna indeks chromatyczny izomorfizm grafów homeomorfizm grafów więcej... Wybrane klasy grafów graf pełny graf spójny drzewo graf dwudzielny graf regularny graf eulerowski graf hamiltonowski graf planarny więcej... Algorytmy grafowe A* Bellmana-Forda Dijkstry Fleury'ego Floyda-Warshalla Johnsona Kruskala Prima przeszukiwanie grafu – wszerz – w głąb najbliższego sąsiada Zagadnienia przedstawiane jako problemy grafowe problem komiwojażera problem chińskiego listonosza problem marszrutyzacji problem kojarzenia małżeństw Inne zagadnienia kod Graya diagram Hassego kod Prüfera

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