Algorytm Dijkstry
Znajduje najtańszą drogę od startu do celu. Zawsze bierze najtańsze miejsce czekające w kolejce priorytetowej, więc koszty rozlewają się od startu jak woda.
- czas O((V + E) log V)
- pamięć O(V)
- używa kolejki priorytetowej
Co to znaczy?
- Koszt: tyle kosztuje ruch. W labiryncie wejście na zwykłe pole kosztuje 1, w błoto 3, a do wody 9; w grafie to liczba na krawędzi.
- Kolejka priorytetowa: kolejka, w której pierwszy idzie najtańszy, a nie ten, kto przyszedł pierwszy.
- Szacunek (h): przewidywany koszt, który jeszcze zostaje. A* pozostaje dokładny tylko wtedy, gdy szacunek nigdy nie jest za wysoki.
- Relaksacja krawędzi: sprawdzenie, czy przejście przez bieżące miejsce daje sąsiadowi niższy koszt, i przyjęcie go, jeśli tak.
- w kolejce
- bieżący
- gotowy
- najtańsza droga
- ziemia · 1
- błoto · 3
- woda · 9
- ściana
Nowy: Start w A1 z kosztem 0. To jedyny element w kolejce.
Spacja: odtwórz lub wstrzymaj. Strzałki lewo/prawo: krok. Home i End: przeskocz.
Spróbuj: Wybierz bagno. Najtańsza droga obchodzi całe błoto dookoła: ma dwa razy więcej ruchów niż prosta linia, a mimo to jest tańsza (34 wobec 36).
Jak to działa
Każde miejsce dostaje koszt: start 0, reszta nieskończoność. Dijkstra trzyma osiągnięte miejsca w kolejce priorytetowej i zawsze bierze najtańsze. Jego koszt jest wtedy ostateczny, bo każda inna droga do niego musiałaby przejść przez coś co najmniej tak samo drogiego. Potem sprawdza sąsiadów: jeśli przejście przez właśnie wzięte miejsce jest tańsze niż dotychczasowy koszt sąsiada, sąsiad dostaje nowy koszt i zapamiętuje, skąd przyszedł. Gdy algorytm weźmie cel, te zapamiętane kroki prowadzą z powrotem najtańszą drogą.
Kiedy warto go użyć
Dijkstry używa się, gdy ruchy kosztują różnie, ale żaden nie kosztuje mniej niż zero: mapy drogowe i nawigacje, routing w sieciach, najtańsze połączenie lotnicze. Gdy każdy ruch kosztuje tyle samo, BFS da tę samą odpowiedź prościej. Przy ujemnych kosztach Dijkstra może się pomylić, a wtedy sprawdza się algorytm Bellmana–Forda.