Algorytm Dijkstry
Algorytm Dijkstry, stworzony przez holenderskiego informatyka Edsgera Dijkstrę, ma na celu znajdowanie najkrótszych ścieżek z określonego wierzchołka do pozostałych w grafie o nieujemnych wagach krawędzi.
Działanie
W przypadku podanego grafu z wyróżnionym wierzchołkiem (źródłem), algorytm oblicza odległości od źródła do wszystkich innych wierzchołków. Można go również zmodyfikować, aby znaleźć jedynie (najkrótszą) ścieżkę do jednego konkretnego wierzchołka, przerywając działanie po dotarciu do wierzchołka docelowego lub transponując tablicę incydencji grafu.
Algorytm Dijkstry identyfikuje w grafie wszystkie najkrótsze ścieżki między wskazanym wierzchołkiem a pozostałymi, jednocześnie obliczając koszt przejścia każdej z tych ścieżek.
Algorytm Dijkstry jest klasycznym przykładem algorytmu zachłannego.
Algorytm
Oznaczmy wierzchołek źródłowy jako s, a wagę krawędzi w(i,j) jako wagę krawędzi (i,j) w grafie.
Utwórz tablicę d odległości od źródła dla wszystkich wierzchołków grafu. Na początku ustawiamy d[s] = 0, a dla wszystkich innych wierzchołków d[v] = ∞.
Stwórz kolejkę priorytetową Q zawierającą wszystkie wierzchołki grafu, gdzie priorytet stanowi aktualnie obliczona odległość od wierzchołka źródłowego s.
Podczas gdy kolejka nie jest pusta:
- Usuń z kolejki wierzchołek u o najniższym priorytecie (najbliższy źródła, który nie został jeszcze rozważony).
- Dla każdego sąsiada v wierzchołka u dokonaj relaksacji:
Jeżeli d[u] + w(u,v) < d[v] (co oznacza, że można szybciej dotrzeć do v przez u), to:
d[v] := d[u] + w(u,v).
Na końcu tablica d będzie zawierać najkrótsze odległości do wszystkich wierzchołków.
Możemy również w tablicy poprzedników przechowywać numer bezpośredniego poprzednika każdego wierzchołka na najkrótszej ścieżce, co umożliwi odtworzenie pełnej ścieżki od źródła do każdego wierzchołka – przy każdej relaksacji w ostatnim punkcie u staje się on poprzednikiem v.
Zastosowanie
Algorytm Dijkstry można wykorzystać przy obliczaniu najkrótszej drogi do wybranej miejscowości. Wystarczy uznać, że każdy punkt skrzyżowania dróg to jeden z wierzchołków grafu, a odległości między punktami to wagi krawędzi.
Jest on również często stosowany w sieciach komputerowych, na przykład przy trasowaniu (np. 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 S zbiór wierzchołków, które zostały już usunięte z kolejki. Dowód opiera się na dwóch faktach (niezmiennikach), które są prawdziwe przez cały czas działania algorytmu:
- Dla każdego wierzchołka v ∈ S, d[v] jest długością najkrótszej ścieżki od s do v.
- Dla każdego wierzchołka v ∉ S, d[v] jest długością najkrótszej ścieżki do v, prowadzącej tylko przez wierzchołki z S.
Na początku oba fakty są oczywiste (zbiór S jest pusty). Po usunięciu wierzchołka u z kolejki, na podstawie faktu 2 wiemy, że nie można do niego dotrzeć 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 co najmniej tak samo długą ścieżkę. Dlatego 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 obejmować wierzchołek u.
Jednakże w takim przypadku musi on być ostatnim wierzchołkiem na tej ścieżce (do każdego innego wierzchołka można by dotrzeć krócej bez używania u), a zatem jej długość wynosi 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 V wierzchołków i E krawędzi grafu. O rzędzie złożoności decyduje sposób implementacji kolejki priorytetowej:
- Używając „naiwnej” implementacji za pomocą tablicy, otrzymujemy złożoność O(V²).
- W przypadku implementacji kolejki za pomocą kopca złożoność wynosi O(E log V).
- Po zastąpieniu zwykłego kopca kopcem Fibonacciego, złożoność zmienia się na O(E + V log V).
Pierwszy wariant jest optymalny dla grafów gęstych (gdy E = Θ(V²)), drugi jest szybszy dla grafów rzadkich (gdy E = Θ(V)), a trzeci rzadko się stosuje z uwagi na skomplikowanie i niewielki przyrost wydajności w porównaniu do niego.
Problemy i algorytmy pokrewne
Algorytm Dijkstry nie działa w przypadku grafów z krawędziami o ujemnych wagach – w takich przypadkach stosuje się wolniejszy, ale bardziej uniwersalny algorytm Bellmana-Forda. Jeżeli graf jest nieważony (wszystkie wagi krawędzi mają wartość 1), można zastosować algorytm przeszukiwania grafu wszerz zamiast algorytmu Dijkstry.
Algorytm A* jest pewnym rozszerzeniem algorytmu Dijkstry, które pozwala na przeszukiwanie tylko części grafu, lecz wymaga dodatkowej informacji (heurystyki) o odległościach między wierzchołkami.
Algorytm Prima, służący do znajdowania minimalnego drzewa rozpinającego, oparty jest na podobnej koncepcji do algorytmu 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.
