- Bieżący
- W kolejce
- Ostateczne
- Ścieżka
Algorytm Dijkstry
Algorytm Dijkstry znajduje najkrótszą drogę od startu do każdego innego wierzchołka, gdy krawędzie mają długości, jak drogi między miastami. Rozrasta się od startu na zewnątrz i zawsze bierze najbliższy wierzchołek, którego jeszcze nie skończył. Kliknij wierzchołek, aby od niego zacząć, wybierz cel, jeśli chcesz, i przejdź krok po kroku, aby zobaczyć kolejkę, każdą odległość malejącą, gdy pojawiają się krótsze drogi, i wyłaniającą się najkrótszą ścieżkę. Naciśnij Odtwórz, aby obejrzeć przeszukiwanie, albo użyj przycisków Krok i Wstecz, aby iść krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Kliknij wierzchołek, aby uczynić go startem; przełącz kliknięcie na Cel i kliknij inny wierzchołek, aby szukać najkrótszej ścieżki do niego. Liczba na każdej krawędzi to jej długość, liczba na każdym wierzchołku to jego najkrótsza dotąd odległość, a rząd pod grafem to kolejka, od najbliższego. Nowy graf tworzy inny graf; wybierz, ile ma mieć wierzchołków i krawędzi. Gdy plansza jest zaznaczona, strzałki przesuwają o krok, spacja odtwarza i wstrzymuje, a Home i End przeskakują na początek i na koniec.
Jak to działa
- Kliknij wierzchołek, aby uczynić go startem. Aby szukać ścieżki, przełącz kliknięcie na Cel i kliknij inny wierzchołek.
- Naciśnij Odtwórz albo użyj przycisków Krok i Wstecz, aby iść krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce przeszukiwania.
- Obserwuj kolejkę pod grafem i odległość na każdym wierzchołku. Nowy graf tworzy inny graf do wypróbowania.
Jak działa algorytm Dijkstry
Daj startowi odległość 0, a każdemu innemu wierzchołkowi nieskończoność, i wstaw start do kolejki. Potem powtarzaj: weź z kolejki wierzchołek o najmniejszej odległości i uznaj tę odległość za ostateczną. Dla każdego jego sąsiada, który nie ma jeszcze ostatecznej odległości, dodaj długość krawędzi do odległości wierzchołka. Jeśli suma jest mniejsza niż dotychczasowa odległość sąsiada, staje się nową odległością, wierzchołek zostaje zapamiętany jako droga do sąsiada, a sąsiad trafia do kolejki, jeśli go w niej nie było. Gdy kolejka jest pusta, każdy osiągalny wierzchołek ma swoją najkrótszą odległość.
Dlaczego odległość najbliższego wierzchołka jest ostateczna
Gdy wierzchołek jest najbliższy w kolejce, każda inna droga do niego musi opuścić gotową część grafu przez jakiś wierzchołek w kolejce, który jest co najmniej tak samo daleko, a potem dodać krawędzie, które nie mogą być ujemne. Żadna inna droga nie może więc być krótsza. Dlatego cel jest pewny dopiero, gdy zostanie wzięty z kolejki, a nie gdy zostanie pierwszy raz osiągnięty, i dlatego algorytm Dijkstry zawodzi przy ujemnych krawędziach: wtedy potrzebny jest algorytm Bellmana–Forda. Gdy każda krawędź ma długość 1, algorytm Dijkstry robi to samo co przeszukiwanie wszerz.
Często zadawane pytania
Czym jest algorytm Dijkstry?
Sposobem na znalezienie najkrótszych ścieżek z jednego wierzchołka startowego do wszystkich innych wierzchołków w grafie, którego krawędzie mają długości równe zero lub większe. Raz za razem bierze najbliższy nieukończony wierzchołek, uznaje jego odległość za ostateczną i używa jego krawędzi, aby skrócić odległości sąsiadów.
Dlaczego algorytm Dijkstry nie działa z ujemnymi krawędziami?
Uznaje odległość wierzchołka za ostateczną, gdy tylko ten wierzchołek jest najbliższy w kolejce. Ujemna krawędź znaleziona później mogłaby jeszcze doprowadzić z powrotem do tego wierzchołka krótszą drogą, więc ostateczna odległość mogłaby być błędna. Algorytm Bellmana–Forda radzi sobie z ujemnymi krawędziami, o ile nie ma cyklu o ujemnej sumie.
Czym różni się Dijkstra od BFS?
Przeszukiwanie wszerz liczy krawędzie i używa zwykłej kolejki. Algorytm Dijkstry sumuje długości krawędzi i używa kolejki priorytetowej, która zawsze daje najbliższy wierzchołek. Gdy każda krawędź ma długość 1, oba znajdują te same odległości.
Jak szybki jest algorytm Dijkstry?
Z kopcem binarnym jako kolejką priorytetową praca rośnie jak (V + E) log V dla V wierzchołków i E krawędzi. Z kopcem Fibonacciego jest to E + V log V. Aplikacja trzyma kolejkę jako posortowaną listę, którą łatwo pokazać i która wystarcza dla małych grafów.
Czy mój graf jest gdzieś wysyłany?
Nie. Graf powstaje i jest przeszukiwany w przeglądarce, a ostatnie ustawienia zostają w jej pamięci lokalnej.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Przejdź do edytora