Algorytm Dijkstry – wprowadzenie

Algorytm Dijkstry służy do wyznaczania najkrótszych ścieżek w grafach skierowanych oraz nieskierowanych o dodatnich wagach. Jego zadaniem jest wyznaczenie najkrótszej ścieżkinajkrótsza ścieżkanajkrótszej ścieżki z wierzchołka początkowego do pozostałych osiągalnych wierzchołków.

R112S9fofqK9B1

Zdjęcie portretowe przedstawia Edsgera W. Dijkstra, twórcę opisywanego algorytmu. starszy mężczyzna ma krótkie, siwe włosy, brodę i wąsy. Nosi okulary. Ubrany jest w jasną koszulę i kamizelę.

Algorytm Dijkstry wykorzystuje podejście zachłanne.

Algorytmy zachłanne charakteryzują się tym, że dokonują wyboru, który jest najlepszy lokalnie, w nadziei na znalezienie najlepszego rozwiązania całego problemu.

Więcej na temat algorytmów zachłannych znajdziesz w e‑materiale Algorytmy zachłanneP1Ed8GL2MAlgorytmy zachłanne i pozostałych e‑materiałach z tej serii.

W kolejnych krokach wybierany jest (spośród tych wierzchołków, które nie zostały jeszcze odwiedzone) ten wierzchołek, do którego prowadzi najkrótsza ścieżka.

Algorytm Dijkstry może przydać ci się przy wyznaczaniu najkrótszej drogi do danego miejsca – w takim wypadku skrzyżowania to węzły grafu, a długości ulic – wagi krawędzi.

Wykorzystuje się go również w sieciach komputerowych, czego przykładem może być trasowanie (z ang. routing), które opisujemy w e‑materiale TrasowaniePmMyRnG3LTrasowanie.

Zasada działania algorytmu

Przyjmijmy następujące założenia:

• analizowany graf to graf spójnygraf spójnygraf spójny o dodatnich wagach;

• wierzchołek s to wierzchołek początkowy, od którego wyznaczane będą ścieżki do wszystkich pozostałych wierzchołków;

• zbiór V to zbiór wszystkich wierzchołków grafu;

• zbiór S będzie zawierał wierzchołki, dla których długości ścieżekdługość ścieżki (koszt dojścia)długości ścieżek zostały już wyznaczone; na samym początku zbiór S jest pusty;

• tablica d[], w której dla każdego wierzchołka przechowujemy wyznaczoną długość ścieżki d[u] z wierzchołka początkowego s;

• tablica p[] jest tablicą poprzedników na najkrótszej ścieżce do wierzchołka początkowego.

Długość ścieżki prowadzącej do wierzchołka początkowego s wynosi 0 (d[s] = 0), a dla wszystkich pozostałych długość ta na początku jest równa ∞. W implementacji zwykle jako nieskończoność przyjmuje się wystarczająco dużą liczbę, co do której mamy pewność, że jest większa niż wartość długości jakiejkolwiek ścieżki – z tego powodu może być też to liczba, która jest większa od liczby wierzchołków pomnożonych przez najdłuższą krawędź grafu.

Lista kroków algorytmu:

1. Tworzymy dwa zbiory wierzchołków – V oraz S.

2. Dla wszystkich wierzchołków grafu (oznaczonych jako u) za wyjątkiem początkowego (oznaczonego jako s) ustawiamy długość ścieżek (czyli elementów tablicy d) na nieskończoność.

3. Wartość d[s] ustawiamy na 0.

4. Ustawiamy poprzednik każdego wierzchołka (elementy tablicy p) jako niezdefiniowany (możemy użyć np. wartości -1).

5. Dopóki zbiór V nie jest pusty:

   • Wybieramy ze zbioru V wierzchołek u o najmniejszym koszcie dojścia do niego (d[u]).

   • Wybrany wierzchołek u usuwamy ze zbioru V i dodajemy do zbioru S.

   • Dla każdego sąsiada wierzchołka u (oznaczonego jako v) sprawdzamy, czy d[v] > d[u] + w(u,v).

     • Jeśli d[v] > d[u] + w(u,v), wyznaczamy nową długość ścieżki do wierzchołka v oraz wierzchołek u zostaje poprzednikiem wierzchołka v.

     • Jeśli nie, nic się nie dzieje.

Przykład wykorzystania

Zastosujmy algorytm Dijkstry dla przykładowego grafu w celu wyznaczenia najkrótszych ścieżek z wierzchołka A do wszystkich pozostałych.

Oto przykładowy graf:

R1JumOOoOfy4z

Ilustracja przedstawia graf z węzłami oznaczonymi literami oraz łączącymi je krawędziami oznaczone cyframi.
A, 4, C. A, 1, B. B, 1, E. B, 6, G. C, 2, G. C, 5, D. D, 12, F. B, 3, F.

Jak już zostało wskazane, wierzchołkiem początkowym jest wierzchołek A.

s = A

Naszym zadaniem jest wyznaczenie najkrótszych ścieżek prowadzących z wierzchołka początkowego A do wszystkich pozostałych wierzchołków oraz najkrótszych ścieżek pomiędzy wierzchołkiem początkowym a wszystkimi pozostałymi.

Tworzymy dwa zbiory.

Zbiór S początkowo jest pusty.

S = { }

Zbiór V zawiera wszystkie wierzchołki zbioru

V = { A, B, C, D, E, F, G }

Tworzymy dwie n-elementowe tablice: d oraz p. Liczba n to liczba wierzchołków grafu.

Tablica d przechowuje długości najkrótszych ścieżek do poszczególnych wierzchołków z wierzchołka początkowego.

Tablica p przechowuje informację na temat poprzedników na ścieżce do danego wierzchołka.

Utwórzmy tabelę, w której będziemy aktualizować stan poszczególnych ścieżek.

Uzupełniamy początkowy stan tabeli zgodnie z krokami 2–4 algorytmu.

W zbiorze V szukamy wierzchołka u o najmniejszym koszcie dojścia do niego (d[u]). To początek wykonywania algorytmu, zatem jest to wierzchołek początkowy, którego d[u] = 0 (ponieważ jest to wierzchołek A, to d[A] = 0). Długości ścieżek do pozostałych wierzchołków są większe.

Wierzchołek przenosimy zatem ze zbioru V do S. Przeglądamy wszystkich sąsiadów przeniesionego wierzchołka. To wierzchołki C oraz B.

d[B] = ∞
d[C] = ∞

d[A] = 0

Sprawdzamy warunek:

d[B] > d[A] + 1

Jest prawdziwy, ponieważ suma 0 oraz 1 jest mniejsza od nieskończoności, zatem:

d[B] ← d[A] + 1

W konsekwencji uzupełniamy pierwszą komórkę tabeli i do p[B] wpisujemy A, czyli poprzednik na ścieżce, a do d[B] wpisujemy 1, czyli długość ścieżki.

Analogicznie postępujemy dla wierzchołka C.

Stan zbiorów:

S = { A }
V = { B, C, D, E, F, G }

Ponownie ze zbioru V wybieramy wierzchołek u o najniższym koszcie dojścia do niego (d[u]).

Tym razem jest to wierzchołek B. Przenosimy go do zbioru S i sprawdzamy jego sąsiadów.

d[A] = 0
d[E] = ∞
d[F] = ∞
d[G] = ∞

d[B] = 1

Sprawdzamy warunki.

d[A] > d[B] + 1
d[E] > d[B] + 1
d[F] > d[B] + 3
d[G] > d[B] + 6

Patrząc od góry, pierwszy warunek nie jest spełniony, ponieważ zero jest mniejsze od 2, zatem przechodzimy dalej.

Pozostałe warunki są spełnione – nieskończoność jest większa od 2, 4 oraz 7.

Zatem:

d[E] ← d[B] + 1
d[F] ← d[B] + 3
d[G] ← D[B] + 6

Uzupełniamy tabelę.

Stan zbiorów:

S = { A, B }
V = { C, D, E, F, G }

Kolejnym wierzchołkiem w zbiorze V, do którego ścieżka (d[u]) jest najkrótsza, jest wierzchołek E.

Przenosimy go do zbioru S i sprawdzamy jego sąsiadów oraz odpowiednie warunki.

d[B] = 1

d[E] = 2

d[B] > d[E] + 1

Nie, zatem nic się nie zmienia.

Stan zbiorów:

S = { A, B, E }
V = { C, D, F, G }

Kolejnym wierzchołkiem w zbiorze V, do którego ścieżka (d[u]) jest najkrótsza, jest wierzchołek C.

Przenosimy go do zbioru S i sprawdzamy jego sąsiadów oraz odpowiednie warunki.

d[A] = 0
d[D] = ∞
d[G] = 7

d[C] = 4

d[A] > d[C] + 4
d[D] > d[C] + 5
d[G] > d[C] + 2

d[D] ← d[C] + 5
d[G] ← d[C] + 2

Uzupełniamy tabelę. Zwróć uwagę, że zmieniamy wcześniej wpisaną wartość.

Stan zbiorów:

S = { A, B, C, E }
V = { D, F, G }

Kolejnym wierzchołkiem w zbiorze V, do którego ścieżka (d[u]) jest najkrótsza, jest wierzchołek G.

Przenosimy go do zbioru S i sprawdzamy jego sąsiadów oraz odpowiednie warunki.

d[B] = 1
d[C] = 4

d[G] = 7

d[B] > d[G] + 6
d[C] > d[G] + 2

W tabeli nic się nie zmienia.

Stan zbiorów:

S = { A, B, C, E, G }
V = { D, F }

Kolejnym wierzchołkiem w zbiorze V, do którego ścieżka (d[u]) jest najkrótsza, jest wierzchołek D.

Przenosimy go do zbioru S i sprawdzamy jego sąsiadów oraz odpowiednie warunki.

d[C] = 4
d[F] = 4

d[D] = 9

d[C] > d[D] + 5
d[F] > d[D] + 12

W tabeli nic się nie zmienia.

Stan zbiorów:

S = { A, B, C, D, E, G }
V = { F }

Ostatnim wierzchołkiem w zbiorze V jest wierzchołek F.

Przenosimy go do zbioru S i sprawdzamy jego sąsiadów oraz odpowiednie warunki.

d[B] = 1
d[D] = 9

d[F] = 4

d[B] > d[F] + 3
d[D] > d[F] + 12

W tabeli nic się nie zmienia.

Uzupełniona tabela prezentuje się następująco:

Algorytm Dijkstry nazywamy zachłannym, ponieważ na każdym etapie dokonuje wyboru lokalnie najkorzystniejszego z nadzieją znalezienia rozwiązania globalnie optymalnego. Taką decyzją jest wybranie wierzchołka o najmniejszym koszcie, a następnie dodanie go do zbioru S.

Zastosowanie algorytmów zachłannych nie zawsze gwarantuje uzyskanie najlepszych możliwych wyników. W przypadku algorytmu Dijkstry rzeczywiście tak jest – odnajdujemy najkrótsze ścieżki.

Słownik