5. Algorytm Dijkstry

Algorytm Dijkstry rozwiązuje problem II, znalezienia najkrótszych ścieżek ze źródła do wszystkich innych wierzchołku grafu, stosując metodę zachłanną. Zakłada się, że graf jest zorientowany i że funkcja kosztu przypisuje krawędziom liczby nieujemne. Przyjmiemy też, że wierzchołki są ponumerowane liczbami naturalnymi od 1 do n, a graf G = jest dany w postaci tablicy list incydencji.

Idea algorytmu

W kolejnych etapach algorytmu zbiór wierzchołków osiągalnych ze źródła s jest powiększany sukcesywnie, o wierzchołki incydentne z ostatnio dołączonymi wierzchołkami. Zawsze staramy się dołączać te wierzchołki, których osiągnięcie wymaga najmniejszego kosztu, które znajdują się najbliżej źródła.

Strukrura danych, użyta w przedstawionej tu implementacji algorytmu Dijkstry, jest bardzo prosta. Długości najkrótszych ścieżek będziemy pamiętali w tablicy d o n pozycjach (n odpowiada liczbie wierzchołków grafu). Ponadto w tablicy P będziemy zapisywali poprzedniki wierzchołków na najkrótszej ścieżce ze źródła.

d[i] = długość najkrótszej ścieżki ze źródła s do wierzchołka i.
p[i] = ojciec (poprzednik) wierzchołka i na najkrótszej ścieżce ze źródła s do i.

Wierzchołki grafu podzielimy na trzy grupy:
S1 - zbiór wierzchołków osiągalnych ze źródła s, dla kórych już znaleziono najkrótszą ścieżkę,
S2 - zbiór wierzchołków, sąsiadujących z wierzchołkami S1, tzn. S2={y: istnieje x w zbiorze S1, że (x,y) należy do E}. S2 jest więc zbiorem wierzchołków, dla których znamy droge ze źródła, ale nie wiemy jeszcze, czy jest to droga najkrótsza.
S3 - zbiór pozostałych wierzchołków, S3 = (V\S1)\S2.

Początkowo S1={s}, S3=V\{s},d(s)=0, a wartością początkową d(x) jest nieskończoność dla wszystkich innych x.

Algorytm

DijkstraSP(G : graf){
	x := s;	//zaczynamy od zródła
	while niepusty(S3) do
	for y takich, że (x,y) należy do E do
	case y w S2
	if d[x] +c(x,y) < d[y] then	// wybieramy krótszą drogę do y
	p[y] := x; d[y] := d[x] + c(x,y);
	fi
	case y w S3	//odległosć od s nie jest ustalona
	S3 := S3\{y}; S2:=S2 + {y};
	p[y] := x; d[y] := d[x] + c(x,y);
	od;
	x := min(S2);	// wybierz wierzchołek z S2 z minimalną wartością d(z)
	od
}

Koszt

Pętla "while" wykonuje się n razy, tyle ile jest elementów w zbiorze wierzchołków grafu. Pętla "for" ma taką długość jak lista incydencji wierzchołka x. Może więc mieć n elementów w najgorszym przypadku. Wybór elementu minimalnego (ze względu na wartość d w zbiorze S2) kosztuje w najgorszym przypadku O(n). Ostatecznie, koszt algorytmu można oszacować z góry przez O(n²).

Przykład 5.1

Rozważmy graf na rysunku 11.5(a). Załóżmy, że wierzchołki zostały ponumerowne zgodnie z porządkiem alfabetycznym i niech zródłem będzie wierzchołek A. Kolejne zmiany stanu struktury zostały zanotowane na rysunku 11.5(c). W kolejnych pozycjach tablicy zaznaczono aktualnie najmniejszą wyliczoną odległość od źródła do wierzchołka wskazanego przez numer kolumny, oraz ojca tego wierzchołka na aktualnie najkrótszej ścieżce. W oststniej kolumnie wypisano wierzchołki należące aktualnie do zbioru S2. Wybrane minimalne elementy zaznaczono kolorem czerwonym. Ostateczny wynik, drzewo najkrótszych ścieżek ze źródła A, został zaznaczony grubą ścieżka na rysunku 11.5(b).


	A	B	C	D	E	F	G	H	I
1		2A				9A	5A			{B,F,G}
2		2A				9A	5A
3			6B			9A	5A			{C,F,G
4			6B			9A	5A
5			6B			9A		10G	7G	{C,F,H,I}
6			6B			9A		10G	7G
7				8C		9A		10G	7G	{D,F,H,I}
8				8C		9A		10G	7G
9				8C	10I	8I		10G		{D,E,F,H}
10				8C	10I	8I		10G
11					9D	8I		9D		{E,F,H}
12					9D	8I		9D		{E,H}
13					9D			9D		{H}
14								9D
		2A	6B	8C	9D	8I	5A	9D	7G
										Rysunek 11.5(c)

Pytanie 6: Czy oszacowanie koszt algorytmu zmieni się, jeśli zbiór S2 zaimplementujemy jako kolejkę priorytetową?