Algorytm Dijkstry — najkrótsza ścieżka krok po kroku

Algorytm Dijkstry wyznacza najkrótsze ścieżki od jednego wierzchołka startowego w grafie ważonym, o ile każda waga krawędzi jest nieujemna. Jeśli interesuje Cię tylko jeden wierzchołek docelowy, możesz zatrzymać się, gdy tylko ten wierzchołek zostanie ustalony.

Podstawowy krok jest zachłanny: zawsze przechodzimy dalej z nieustalonego wierzchołka o najmniejszej znanej odległości. To działa tylko przy założeniu nieujemnych wag.

Co rozwiązuje algorytm Dijkstry

Użyj algorytmu Dijkstry, gdy masz graf z kosztami na krawędziach i chcesz znaleźć najtańszą trasę. Koszt może oznaczać odległość, czas przejazdu, energię albo inną wielkość, którą chcesz zminimalizować.

Działa zarówno dla grafów skierowanych, jak i nieskierowanych. Kluczowy warunek jest jasny: każda waga krawędzi musi być co najmniej równa $0$.

Jak działa algorytm

Każdy wierzchołek przechowuje tymczasową odległość od wierzchołka startowego. Na początku wierzchołek startowy ma odległość $0$, a każdy inny wierzchołek ma odległość $\infty$.

Następnie powtarzamy tę pętlę:

1. Wybierz nieustalony wierzchołek o najmniejszej tymczasowej odległości.
2. Sprawdź każdego sąsiada przez ten wierzchołek.
3. Jeśli nowa trasa jest tańsza, zaktualizuj odległość sąsiada.
4. Oznacz bieżący wierzchołek jako ustalony.

Krok 3 nazywa się relaksacją. Ustalony wierzchołek jest zakończony: jego najkrótsza odległość jest ostateczna, pod warunkiem że graf nie ma krawędzi o ujemnych wagach.

Algorytm Dijkstry krok po kroku

Oto pełna procedura w zwartej postaci:

1. Wybierz wierzchołek startowy.
2. Ustaw jego odległość na $0$, a każdą inną odległość na $\infty$.
3. Wybierz nieustalony wierzchołek o najmniejszej tymczasowej odległości.
4. Wykonaj relaksację jego krawędzi wychodzących.
5. Oznacz ten wierzchołek jako ustalony.
6. Powtarzaj, aż wszystkie osiągalne wierzchołki zostaną ustalone, albo zatrzymaj się, gdy ustalony zostanie wierzchołek docelowy.

Jeśli dodatkowo zapisujesz, który poprzedni wierzchołek spowodował każdą aktualizację, możesz odtworzyć rzeczywistą ścieżkę, a nie tylko końcową odległość.

Przykład wyznaczania najkrótszej ścieżki

Załóżmy, że graf ma następujące wagi krawędzi:

• $A \to B = 4$
• $A \to C = 1$
• $C \to B = 2$
• $B \to D = 1$
• $C \to D = 5$

Chcemy znaleźć najkrótszą ścieżkę z $A$ do $D$.

Zaczynamy od:

$$\text{dist}(A)=0,\quad \text{dist}(B)=\infty,\quad \text{dist}(C)=\infty,\quad \text{dist}(D)=\infty$$

Najpierw ustalamy $A$ i wykonujemy relaksację jego krawędzi:

$$\text{dist}(B)=4,\quad \text{dist}(C)=1$$

Najmniejsza nieustalona odległość jest teraz przy $C$, więc jako następny ustalamy $C$.

Przechodząc przez $C$:

• Przez $C$ ścieżka do $B$ ma koszt $1+2=3$, co poprawia wynik $4$, więc aktualizujemy $\text{dist}(B)=3$.
• Przez $C$ ścieżka do $D$ ma koszt $1+5=6$, więc ustawiamy $\text{dist}(D)=6$.

Teraz $B$ ma najmniejszą nieustaloną odległość, więc ustalamy $B$.

Przechodząc przez $B$, ścieżka do $D$ ma koszt:

$$3+1=4$$

To poprawia wynik $6$, więc aktualizujemy $\text{dist}(D)$ z $6$ na $4$.

Teraz $D$ jest nieustalonym wierzchołkiem o najmniejszej odległości. Ustalamy go i kończymy.

Najkrótsza ścieżka to:

$$A \to C \to B \to D$$

o łącznym koszcie:

$$1+2+1=4$$

Ten przykład pokazuje kluczowy schemat: trasa, która na początku wyglądała gorzej, $A \to B$, później stała się lepsza dzięki przejściu przez $C$. Algorytm Dijkstry na to pozwala, dopóki $B$ pozostaje nieustalony. Gdy wierzchołek zostanie ustalony, jego odległość już się nie zmieni.

Dlaczego nieujemne wagi są ważne

Załóżmy, że obecnie najtańszy nieustalony wierzchołek ma odległość $d$. Każda nowa ścieżka do tego wierzchołka znaleziona później musiałaby wychodzić z innego nieustalonego wierzchołka, którego tymczasowa odległość wynosi co najmniej $d$, a potem dodać krawędź o wadze co najmniej $0$.

Taka późniejsza trasa nie może więc dać wyniku lepszego niż $d$. Dlatego ustalanie najmniejszej tymczasowej odległości jest bezpieczne, gdy wszystkie wagi są nieujemne.

Jeśli istnieje krawędź o ujemnej wadze, ten argument przestaje działać. Ścieżka, która teraz wygląda na drogą, może później stać się tańsza, co oznacza, że zbyt wczesne ustalenie wierzchołka może dać błędną odpowiedź.

Typowe błędy w algorytmie Dijkstry

Używanie go przy ujemnej krawędzi

Nawet jedna ujemna krawędź może zniszczyć logikę zachłanną. Jeśli mogą wystąpić ujemne wagi, użyj innej metody wyznaczania najkrótszej ścieżki.

Traktowanie „widziany” jako „zakończony”

Wierzchołek może już mieć tymczasową odległość i nadal nie być zakończony. Tylko ustalony wierzchołek ma ostateczną najkrótszą odległość.

Zapominanie o tabeli poprzedników

Odległości mówią, jaki jest koszt. Jeśli chcesz też znać samą trasę, zapisuj, który wierzchołek jako ostatni poprawił każdą odległość.

Gdzie używa się algorytmu Dijkstry

Algorytm Dijkstry stosuje się wtedy, gdy problem można zamodelować jako poruszanie się po grafie z nieujemnymi kosztami:

• Planowanie tras na mapach
• Routing sieciowy
• Ruch robota na ważonych siatkach
• Wyznaczanie ścieżek w grach, gdy koszty ruchu są różne

To także standardowy przykład algorytmu zachłannego, którego poprawność zależy od precyzyjnego warunku.

Spróbuj podobnego zadania

Narysuj graf z pięcioma wierzchołkami i dodatnimi wagami krawędzi, a potem wykonaj algorytm Dijkstry ręcznie, używając tabeli odległości. Jeśli chcesz zrobić kolejny krok, spróbuj własnej wersji na nowym grafie i sprawdź dokładnie, w którym momencie każdy wierzchołek staje się bezpieczny do ustalenia.