Algorytm Dijkstry służy do znajdowania najkrótszych dróg w grafie, w którym krawędzie mają przypisane nieujemne wagi. W praktyce można myśleć o nim jak o szukaniu najtańszej trasy z jednego punktu do wszystkich pozostałych. Wagą może być odległość, czas przejazdu, koszt albo dowolna inna wartość, którą chcemy minimalizować. Algorytm nie wybiera po prostu drogi z najmniejszą liczbą połączeń - interesuje go suma wag. To ważna różnica, bo trasa prowadząca przez trzy wierzchołki może okazać się krótsza od bezpośredniego połączenia.
- Co właściwie robi algorytm Dijkstry?
- Najkrótsza ścieżka nie zawsze ma najmniej krawędzi
- Jak działa algorytm Dijkstry?
- Relaksacja krawędzi - o co w niej chodzi?
- Algorytm Dijkstry krok po kroku - przykład
- Algorytm Dijkstry w Pythonie
- Co dzieje się w kodzie?
- Jak odtworzyć najkrótszą ścieżkę?
- Dlaczego Dijkstra nie działa z ujemnymi wagami?
- Dijkstra, BFS czy Bellman-Ford?
- Złożoność algorytmu Dijkstry
- Gdzie wykorzystuje się algorytm Dijkstry?
- FAQ - algorytm Dijkstry
Co właściwie robi algorytm Dijkstry?
Najprościej wyobrazić sobie kilka miast połączonych drogami. Każda droga ma określoną długość. Zaczynamy w mieście A i chcemy wiedzieć, ile wynosi najkrótsza trasa do B, C, D i wszystkich pozostałych miejsc.
Można oczywiście próbować sprawdzać kolejne możliwe drogi, ale liczba kombinacji szybko rośnie. Algorytm Dijkstry podchodzi do problemu inaczej. Stopniowo odkrywa coraz dalsze wierzchołki, zawsze zaczynając od tego, do którego znamy obecnie najkrótszą drogę.
Dla każdego wierzchołka przechowujemy najlepszą znaną w danym momencie odległość od punktu startowego. Początkowo znamy tylko jedną pewną wartość:
start = 0
Do wszystkich pozostałych wierzchołków przypisujemy na początku nieskończoność:
A = 0 B = ∞ C = ∞ D = ∞
Nie oznacza to, że nie da się do nich dotrzeć. Po prostu na tym etapie nie znamy jeszcze żadnej trasy.
Najkrótsza ścieżka nie zawsze ma najmniej krawędzi
To jedna z rzeczy, które na początku potrafią trochę mylić. W grafie ważonym "najkrótsza" oznacza najmniejszą sumę wag, a nie najmniejszą liczbę przejść.
Załóżmy, że mamy takie połączenia:
A → D = 10 A → B = 2 B → C = 2 C → D = 2
Bezpośrednia droga z A do D ma tylko jedną krawędź, ale jej koszt wynosi 10.
Trasa:
A → B → C → D
składa się z trzech krawędzi, lecz jej całkowity koszt wynosi:
2 + 2 + 2 = 6
To właśnie tę trasę uznamy za krótszą. Dijkstra patrzy więc na koszt całej drogi, a nie na to, ile wierzchołków po drodze odwiedziliśmy.
Jak działa algorytm Dijkstry?
Schemat działania można opisać bez matematycznych skrótów. Zaczynamy od punktu startowego i sprawdzamy, dokąd można z niego przejść bezpośrednio.
Następnie wybieramy wierzchołek, do którego znamy najmniejszy koszt. Traktujemy go jako kolejny punkt, z którego sprawdzamy dalsze połączenia.
- Ustaw odległość wierzchołka startowego na 0.
- Wszystkim pozostałym przypisz początkowo nieskończoność.
- Wybierz wierzchołek o najmniejszej znanej odległości.
- Sprawdź jego sąsiadów.
- Policz, ile kosztowałaby droga do każdego z nich przez aktualny wierzchołek.
- Jeżeli nowa droga jest krótsza od dotychczas znanej, zapisz nową wartość.
- Przejdź do kolejnego wierzchołka o najmniejszej odległości.
- Powtarzaj, aż nie zostanie nic do sprawdzenia.
Najważniejszy moment pojawia się w punkcie piątym i szóstym. To właśnie tam algorytm odkrywa, że do danego miejsca da się dotrzeć krócej niż wcześniej sądziliśmy.
Relaksacja krawędzi - o co w niej chodzi?
W opisach algorytmu Dijkstry często pojawia się termin "relaksacja krawędzi". Nazwa brzmi poważnie, ale sama operacja jest bardzo prosta.
Załóżmy, że wiemy już, iż dotarcie z A do B kosztuje 3. Z B prowadzi krawędź do C o wadze 2.
Droga z A do C przez B kosztowałaby więc:
3 + 2 = 5
Jeżeli wcześniej mieliśmy zapisane:
C = 8
to znaleźliśmy lepszą trasę i zmieniamy wartość:
C = 5
Jeśli natomiast wcześniej C miało już odległość 4, niczego nie zmieniamy. Droga kosztująca 5 nie daje nam przecież żadnej korzyści.
W kodzie sprowadza się to właściwie do jednego warunku:
if nowa_odleglosc < odleglosci[sasiad]:
odleglosci[sasiad] = nowa_odleglosc
Algorytm Dijkstry krok po kroku - przykład
Przejdźmy przez prosty graf. Mamy cztery wierzchołki: A, B, C i D oraz następujące połączenia:
A → B = 1 A → C = 4 B → C = 2 B → D = 5 C → D = 1
Zaczynamy w wierzchołku A.
Krok 1 - start w A
Na początku:
A = 0 B = ∞ C = ∞ D = ∞
Z A możemy przejść do B kosztem 1 oraz do C kosztem 4. Aktualizujemy więc odległości:
A = 0 B = 1 C = 4 D = ∞
Krok 2 - wybieramy B
Spośród nieprzetworzonych wierzchołków najmniejszą odległość ma B, czyli 1.
Z B możemy przejść do C kosztem 2. Cała droga A → B → C kosztuje:
1 + 2 = 3
Do tej pory mieliśmy zapisane C = 4. Znaleźliśmy więc lepszą trasę:
C = 3
Z B prowadzi też droga do D o wadze 5:
1 + 5 = 6
Pierwsza znana odległość do D wynosi więc 6.
A = 0 B = 1 C = 3 D = 6
Krok 3 - przechodzimy do C
Kolejną najmniejszą odległość ma C: 3.
Z C możemy dotrzeć do D za 1. Otrzymujemy:
3 + 1 = 4
Dotychczas znana trasa do D kosztowała 6, więc ponownie mamy poprawę:
D = 4
Krok 4 - zostaje D
Najkrótsza znana odległość do D wynosi 4. Nie ma już niczego, co pozwalałoby ją zmniejszyć.
Końcowe wyniki wyglądają więc tak:
| Wierzchołek | Najkrótsza odległość od A | Najkrótsza droga |
|---|---|---|
| A | 0 | A |
| B | 1 | A → B |
| C | 3 | A → B → C |
| D | 4 | A → B → C → D |
To dobry przykład pokazujący, że pierwsza znaleziona droga wcale nie musi być najlepsza. Najpierw do C znaliśmy trasę o koszcie 4, potem znaleźliśmy 3. Do D najpierw doszliśmy z wynikiem 6, a chwilę później poprawiliśmy go do 4.
Algorytm Dijkstry w Pythonie
W Pythonie wygodnie wykorzystać moduł heapq. Pozwala on przechowywać wierzchołki w taki sposób, aby łatwo pobierać ten o najmniejszej aktualnej odległości.
import heapq
def dijkstra(graf, start):
odleglosci = {wierzcholek: float('inf') for wierzcholek in graf}
odleglosci[start] = 0
kolejka = [(0, start)]
while kolejka:
aktualna_odleglosc, wierzcholek = heapq.heappop(kolejka)
if aktualna_odleglosc > odleglosci[wierzcholek]:
continue
for sasiad, waga in graf[wierzcholek].items():
nowa_odleglosc = aktualna_odleglosc + waga
if nowa_odleglosc < odleglosci[sasiad]:
odleglosci[sasiad] = nowa_odleglosc
heapq.heappush(kolejka, (nowa_odleglosc, sasiad))
return odleglosci
graf = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
wynik = dijkstra(graf, 'A')
print(wynik)
Program zwróci:
{'A': 0, 'B': 1, 'C': 3, 'D': 4}
Wynik zgadza się więc z tym, co wcześniej policzyliśmy ręcznie.
Co dzieje się w kodzie?
Najpierw dla każdego wierzchołka tworzymy wartość nieskończoną:
odleglosci = {wierzcholek: float('inf') for wierzcholek in graf}
Tylko punkt startowy otrzymuje wartość 0:
odleglosci[start] = 0
Do kolejki trafia para:
(0, start)
Pierwsza wartość oznacza koszt dotarcia, druga konkretny wierzchołek. Moduł heapq działa jako kopiec minimum, więc heappop() pobiera element o najmniejszej wartości znajdującej się na początku krotki.
Następnie sprawdzamy wszystkie połączenia wychodzące z aktualnego wierzchołka:
for sasiad, waga in graf[wierzcholek].items():
Wyliczamy koszt dotarcia do sąsiada:
nowa_odleglosc = aktualna_odleglosc + waga
Jeśli jest niższy niż wcześniej zapisany wynik, aktualizujemy odległość i dodajemy nową parę do kolejki.
W kodzie znajduje się jeszcze fragment:
if aktualna_odleglosc > odleglosci[wierzcholek]:
continue
Jest potrzebny dlatego, że ten sam wierzchołek może trafić do kolejki więcej niż raz. Jeśli później znajdziemy do niego krótszą drogę, starszy wpis nadal może pozostać w kopcu. Po jego pobraniu po prostu go pomijamy.
Jak odtworzyć najkrótszą ścieżkę?
Dotychczasowy program podaje jedynie odległości. Często chcemy jednak wiedzieć nie tylko, że z A do D jest 4, ale również którędy należy przejść.
W takim przypadku podczas aktualizowania odległości zapamiętujemy poprzedni wierzchołek.
import heapq
def dijkstra(graf, start):
odleglosci = {w: float('inf') for w in graf}
poprzedni = {w: None for w in graf}
odleglosci[start] = 0
kolejka = [(0, start)]
while kolejka:
aktualna_odleglosc, wierzcholek = heapq.heappop(kolejka)
if aktualna_odleglosc > odleglosci[wierzcholek]:
continue
for sasiad, waga in graf[wierzcholek].items():
nowa_odleglosc = aktualna_odleglosc + waga
if nowa_odleglosc < odleglosci[sasiad]:
odleglosci[sasiad] = nowa_odleglosc
poprzedni[sasiad] = wierzcholek
heapq.heappush(kolejka, (nowa_odleglosc, sasiad))
return odleglosci, poprzedni
Dla naszego przykładu zapis poprzedników będzie wskazywał:
B ← A C ← B D ← C
Czytając od końca, otrzymujemy:
D ← C ← B ← A
Po odwróceniu kolejności mamy właściwą trasę:
A → B → C → D
To właśnie taki mechanizm pozwala później wyświetlić użytkownikowi nie tylko koszt przejazdu, ale również kolejne punkty wybranej drogi.
Dlaczego Dijkstra nie działa z ujemnymi wagami?
To jedno z najważniejszych ograniczeń tego algorytmu. Dijkstra zakłada, że wagi krawędzi są nieujemne.
Powód jest związany ze sposobem wybierania kolejnych wierzchołków. Gdy algorytm uzna, że znalazł najkrótszą drogę do danego miejsca, opiera się na założeniu, że dalsze przejścia nie zmniejszą już jej kosztu.
Przy dodatnich wagach ma to sens. Jeżeli obecny koszt wynosi 5, dodanie kolejnej krawędzi o wadze 2 da 7, a nie 3.
W przypadku ujemnej krawędzi sytuacja wygląda inaczej:
5 + (-4) = 1
Nagle trasa, którą wcześniej uznaliśmy za gorszą, może po przejściu przez ujemną krawędź okazać się tańsza.
Dlatego w grafach zawierających ujemne wagi trzeba zastosować inny algorytm, na przykład Bellmana-Forda.
Dijkstra, BFS czy Bellman-Ford?
Nie każdy problem ze znajdowaniem drogi wymaga algorytmu Dijkstry. Wybór zależy przede wszystkim od tego, jakie dane znajdują się w grafie.
| Sytuacja | Algorytm |
|---|---|
| Graf bez wag lub wszystkie krawędzie mają taki sam koszt | BFS |
| Graf z nieujemnymi wagami | Dijkstra |
| Graf może zawierać ujemne wagi | Bellman-Ford |
Jeżeli wszystkie drogi mają koszt 1, stosowanie Dijkstry zwykle nie jest potrzebne. BFS znajdzie najkrótszą drogę prościej.
Jeżeli natomiast poszczególne połączenia mają różne dodatnie koszty - na przykład 2, 7, 15 czy 120 - Dijkstra jest naturalnym rozwiązaniem.
Złożoność algorytmu Dijkstry
Czas działania zależy od sposobu przechowywania grafu i wybierania kolejnego wierzchołka.
W wersji wykorzystującej listę sąsiedztwa i kolejkę priorytetową opartą na kopcu złożoność zapisuje się zwykle jako:
O((V + E) log V)
Dla grafu spójnego często spotkamy też skrócony zapis:
O(E log V)
gdzie:
- V oznacza liczbę wierzchołków,
- E oznacza liczbę krawędzi.
Pamięć potrzebna jest między innymi na graf, tablicę lub słownik odległości oraz kolejkę priorytetową. Przy reprezentacji listą sąsiedztwa można przyjąć rząd O(V + E).
Dla osoby uczącej się algorytmu ważniejsze od samego wzoru jest jednak to, skąd bierze się jego sprawność. Zamiast za każdym razem przeglądać wszystkie możliwe wierzchołki, kolejka priorytetowa pozwala szybko wybrać ten z najmniejszą aktualnie znaną odległością.
Gdzie wykorzystuje się algorytm Dijkstry?
Najbardziej oczywiste skojarzenie to nawigacja. Skrzyżowania można potraktować jako wierzchołki, drogi jako krawędzie, a ich długość lub czas przejazdu jako wagi.
Taki model pozwala szukać trasy o najmniejszym koszcie. Nie musi to być zresztą fizyczna odległość. Wagą może być czas, koszt przejazdu czy inna liczba opisująca dane połączenie.
Podobny problem pojawia się w sieciach komputerowych. Wierzchołkami mogą być urządzenia, a krawędziami połączenia pomiędzy nimi. W zależności od modelu wagą może być koszt trasy lub inna metryka opisująca dane połączenie.
Algorytmy najkrótszej ścieżki pojawiają się także w logistyce, analizie sieci, grach oraz wszędzie tam, gdzie mamy zbiór punktów połączonych trasami o różnych kosztach.
Dijkstra jest przy tym dobrym algorytmem do nauki grafów, bo łączy kilka tematów naraz: reprezentację grafu, kolejkę priorytetową, aktualizowanie odległości i odtwarzanie ścieżki.
Komentarze