Algorytm Dijkstry służy do wyznaczania najmniejszej odległości od ustalonego wierzchołka s do wszystkich pozostałych w skierowanym grafie, w odróżnieniu jednak od Algorytmu Forda-Bellmana, graf wejściowy nie może zawierać krawędzi o ujemnych wagach.
W algorytmie tym pamiętany jest zbiór Q wierzchołków, dla których nie obliczono jeszcze najkrótszych ścieżek, oraz wektor D[i] odległości od wierzchołka s do i. Początkowo zbiór Q zawiera wszystkie wierzchołki a wektor D jest pierwszym wierszem macierzy wag krawędzi A.
Algorytm przebiega następująco:

1. Dopóki zbiór Q nie jest pusty wykonuj:
2. Pobierz ze zbioru Q wierzchołek v o najmniejszej wartości D[v] i usuń go ze zbioru.
3. Dla każdego następnika i wierzchołka v dokonaj relaksacji ścieżki, tzn. sprwdź, czy D[i]>D[v]+A[v,i], tzn czy aktualne oszacowanie odległości do wierzchołka i jest większe od oszacowania odległości do wierzchołka v plus waga krawędzi (v,i).
   Jeżeli tak jest, to zaktualizuj oszacowanie D[i] przypisując mu prawą stronę nierówności (czyli mniejszą wartość).

Jak widać z powyższego pseudokodu, algorytm wybiera z kolejki Q "najlżejszy" wierzchołek, tzn. jest oparty o strategię zachłanną.
Wprawdzie metoda zachłanna nie zawsze daje wynik optymalny, jednak algorytm Dijkstry jest algorytmem dokładnym.
Oto przyładowy graf oraz jego macierz wag krawędzi (nieskończoność oznacza brak krawędzi):
Obliczenia przebiegają następująco: (Dla S=a)
(gwiazdka oznacza symbol nieskończoności, najlżejszy wierzchołek jest podkreślony, wierzchołki, dla których wyznaczono już najkrótsze ścieżki są pogrubione)

Q	D(a)	D(b)	D(c)	D(d)	D(e)
{b,c,d,e}	0	10	*	*	5
{b,c,d}	0	8	14	7	5
{b,c}	0	8	13	7	5
{c}	0	8	9	7	5
{}	0	8	9	7	5

Istnieje kilka odmian implementacji Dijkstry; najprostsza używa tablicy do przechowywania wierzchołków ze zbiory Q. Inne wersje algorytmu używają kolejki priorytetowej lub kopca Fibonacciego.
Po znalezieniu najkrótszej odległości między wierzchołkami możemy znaleźć drogę łączącą te wierzchołki za pomocą algorytmu konstrukcji drogi.
Złożoność obliczeniowa: O(n²), przy implementacji bez użycia kopca. Z użyciem kopca można zejść do O(n log n).

Komentarze