Algorytm Dijkstry
Twój planer tras zna najszybszą drogę spod twoich drzwi niemal w każde miejsce. U podstaw tego pomysłu leży algorytm, który Edsger Dijkstra wymyślił w 1956 roku w około dwadzieścia minut: rozrastaj się od startu na zewnątrz i zawsze najpierw kończ najbliższe miejsce.
Idea
Wyobraź sobie miasta połączone drogami o różnych długościach. Pytanie brzmi: jaka jest najkrótsza droga z mojego miasta do każdego innego? Przeszukiwanie wszerz odpowiada na nie, gdy każda droga liczy się tak samo, ale tutaj trasa z większą liczbą dróg może być krótsza. Algorytm Dijkstry przechowuje dla każdego miasta najkrótszą znalezioną dotąd odległość i powiększa obszar miast o pewnej odległości, zawsze dodając najbliższe miasto, którego odległość nie jest jeszcze pewna.
Krok po kroku
Daj startowi odległość 0, a każdemu innemu wierzchołkowi nieskończoność. Wstaw start do kolejki priorytetowej, czyli kolejki, która zawsze wydaje wierzchołek o najmniejszej odległości. Weź ten wierzchołek; jego odległość jest teraz ostateczna. Dla każdego sąsiada bez ostatecznej odległości oblicz odległość przez ten wierzchołek: jego odległość plus długość krawędzi. Jeśli wynik jest mniejszy niż dotychczasowa odległość sąsiada, zmniejsz ją, zapamiętaj ten wierzchołek jako drogę do sąsiada i wstaw sąsiada do kolejki. Nazywa się to relaksacją krawędzi. Powtarzaj, aż kolejka będzie pusta albo aż cel zostanie z niej wzięty.
Przykład
Weź krawędzie A–B o długości 4, A–C 1, B–C 2, B–D 1, C–D 5 i D–E 3 i zacznij od A. Wzięcie A daje B odległość 4, a C odległość 1. C jest najbliżej, więc ma ostateczną odległość 1; przez C odległość B spada do 1 + 2 = 3, a D dostaje 1 + 5 = 6. Teraz najbliżej jest B, z ostateczną odległością 3, i przez B odległość D spada do 3 + 1 = 4. D ma ostateczną odległość 4 i daje E 4 + 3 = 7. Najkrótsza droga z A do E to więc A → C → B → D → E o długości 7, choć A → B → D → E ma mniej krawędzi i długość 8.
Dlaczego to działa
Załóżmy, że wierzchołek X jest najbliższy w kolejce, w odległości d. Każda inna droga od startu do X musi w pewnym momencie opuścić obszar wierzchołków o ostatecznej odległości, a pierwszy wierzchołek, do którego dociera poza tym obszarem, jest w kolejce, więc jest już co najmniej d od startu. Reszta drogi nie może jej skrócić, bo żadna krawędź nie jest ujemna. Zatem d to najkrótsza odległość do X. Przy ujemnej krawędzi to rozumowanie zawodzi; wtedy używa się algorytmu Bellmana–Forda, który relaksuje każdą krawędź raz po raz.
Historia i zastosowania
Edsger W. Dijkstra opracował algorytm w 1956 roku, aby pokazać możliwości nowego komputera ARMAC w Amsterdamie, wyznaczając trasy między holenderskimi miastami, i opublikował go w 1959 roku. Ten sam pomysł, z lepszą kolejką, działa w planerach tras i w internetowych protokołach routingu, takich jak OSPF i IS-IS, które wyznaczają najkrótszą drogę danych między routerami. Przeszukiwanie A* dodaje oszacowanie odległości, która jeszcze została, dzięki czemu może kierować się do celu i sprawdzać mniej wierzchołków.
Wypróbuj
Otwórz aplikację i naciśnij Krok. Liczby na krawędziach to ich długości, a liczba na każdym wierzchołku to jego dotychczasowa odległość. Wierzchołki w kolejce są niebieskie, ostateczne – zielone, a kolejka pod grafem pokazuje je z odległościami, od najbliższego. Wypatruj chwil, gdy odległość spada, bo trasa, która wyglądała na dłuższą, okazuje się krótsza, i wybierz cel, aby zobaczyć, jak przeszukiwanie kończy się, gdy tylko odległość celu jest ostateczna.
Często zadawane pytania
Jaka jest złożoność czasowa algorytmu Dijkstry?
Zależy od kolejki priorytetowej. Z prostą listą to O(V²) dla V wierzchołków; z kopcem binarnym O((V + E) log V) dla E krawędzi; z kopcem Fibonacciego O(E + V log V), jak pokazali Michael Fredman i Robert Tarjan w 1984 roku.
Czy algorytm Dijkstry radzi sobie z ujemnymi wagami krawędzi?
Nie. Zakłada, że odległość wierzchołka nie może się poprawić, gdy ten jest już najbliższy w kolejce, a ujemna krawędź może to złamać. Dla grafów z ujemnymi krawędziami użyj algorytmu Bellmana–Forda.
Czy algorytm Dijkstry znajduje ścieżkę do każdego wierzchołka?
Tak. Uruchomiony do końca daje najkrótszą odległość od startu do każdego osiągalnego wierzchołka, a zapamiętane wierzchołki tworzą drzewo najkrótszych ścieżek. Zatrzymanie się wcześniej, gdy odległość celu jest ostateczna, oszczędza pracę, gdy potrzebna jest tylko jedna ścieżka.
Jak algorytm Dijkstry ma się do A*?
Przeszukiwanie A* to algorytm Dijkstry z podpowiedzią: porządkuje kolejkę według dotychczasowej odległości plus oszacowania odległości, która jeszcze została, na przykład odległości w linii prostej na mapie. Z dobrym oszacowaniem znajduje tę samą najkrótszą ścieżkę, sprawdzając znacznie mniej wierzchołków.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Wypróbuj algorytm Dijkstry