Algorytm Dijkstry
Z Wikipedii
Niniejszy artykuł jest częścią cyklu teoria grafów.
 |
|
Najważniejsze pojęcia Wybrane klasy grafów Algorytmy grafowe Zagadnienia przedstawiane jako problemy grafowe Inne zagadnienia |
| edytuj ten szablon |
Algorytm Dijkstry, odkryty 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. Jest często używany w routingu.
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 ścieżki do jednego ustalonego wierzchołka, po prostu przerywając działanie w momencie dojścia do wierzchołka docelowego.
Algorytm Dijkstry jest przykładem algorytmu zachłannego.
Spis treści |
[edytuj] Algorytm
Przez s oznaczamy wierzchołek źródłowy, w(i,j) to waga krawędzi (i,j) w grafie.
- Stwórz tablicę d odległości od źródła dla wszystkich wierzchołków grafu. Na początku d[s] = 0, zaś d[v] = nieskończoność dla wszystkich pozostałych wierzchołków.
- Utwórz kolejkę priorytetową Q wszystkich wierzchołków grafu. Priorytetem kolejki jest aktualnie wyliczona odległość od wierzchołka źródłowego s.
- Dopóki kolejka nie jest pusta:
- Usuń z kolejki wierzchołek u o najniższym priorytecie (wierzchołek najbliższy źródła, który nie został jeszcze rozważony)
- Dla każdego sąsiada v wierzchołka u dokonaj relaksacji poprzez u: jeśli d[u] + w(u,v) < d[v] (poprzez u da się dojść do v szybciej niż dotychczasową ścieżką), to d[v]: = d[u] + w(u,v).
Na końcu tablica 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, u staje się poprzednikiem v.
[edytuj] 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
[edytuj] Dowód poprawności
Oznaczmy przez 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:
- Dla każdego wierzchołka
, liczba d[v] jest długością najkrótszej ścieżki od s do v. - Dla każdego wierzchołka
, d[v] jest długością najkrótszej krawędzi do v prowadzącej tylko przez wierzchołki z S.
Na początku oba fakty są oczywiste (S jest zbiorem pustym). Przy zdejmowaniu wierzchołka u z kolejki wiemy, na podstawie faktu 2, że nie da się do niego dojść żadną krótszą drogą przez wierzchołki z S. Z drugiej strony, ponieważ u ma najniższy priorytet, przejście przez jakikolwiek inny wierzchołek spoza S dałoby od razu co najmniej tak samo długą ścieżkę. A zatem dołączając wierzchołek u do S zachowujemy prawdziwość faktu 1. Następnie musimy uwzględnić fakt, że najkrótsza ścieżka do jakiegoś wierzchołka v po wierzchołkach z nowego zbioru S może teraz zawierać wierzchołek u. Ale wtedy musi on być ostatnim na niej wierzchołkiem (do każdego innego dałoby się dojśc krócej nie używając u), a zatem jej długość równa jest d[u] + w(u,v) i zostanie prawidłowo obliczona w następnym kroku algorytmu.
[edytuj] Złożoność
Złożoność obliczeniowa algorytmu Dijkstry zależy od liczby V wierzchołków i 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 O(V2)
- w implementacji kolejki poprzez kopiec, złożoność wynosi O(ElogV)
- po zastąpieniu zwykłego kopca kopcem Fibonacciego, złożoność zmniejsza się do O(E + VlogV)
Pierwszy wariant jest optymalny dla grafów gęstych (czyli jeśli E = Θ(V2)), drugi jest szybszy dla grafów rzadkich (E = Θ(V)), trzeci jest bardzo rzadko używany ze względu na duży stopień skomplikowania i niewielki w porównaniu z nim zysk czasowy.
[edytuj] 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.
[edytuj] Zobacz też
[edytuj] 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.
