- Bieżący przystanek
- Był już przystankiem
- Skrócona para
- Ścieżka
Algorytm Floyda–Warshalla
Jak daleko jest z każdego miasta do każdego innego? Algorytm Floyda–Warshalla odpowiada na to za jednym razem, za pomocą tabeli i trzech zagnieżdżonych pętli. Każda runda dopuszcza jeszcze jeden wierzchołek jako przystanek po drodze i dla każdej pary sprawdza, czy objazd przez niego jest krótszy. Idź krok po kroku i zobacz, jak tabela się wypełnia, a odległości maleją. Naciśnij Odtwórz, aby zobaczyć, jak wypełnia się tabela, albo użyj przycisków Krok i Wstecz, aby iść krok po kroku. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Tabela zawiera najkrótszą dotąd znalezioną odległość między każdą parą wierzchołków; liczba na każdej krawędzi to jej długość. Każda runda dopuszcza jeszcze jeden wierzchołek jako przystanek po drodze, a każdy krok pokazuje parę, która dzięki niemu się skraca. Kliknij wierzchołek, aby uczynić go startem; przełącz kliknięcie na Cel i kliknij inny wierzchołek, aby na końcu zobaczyć najkrótszą ścieżkę między nimi. 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
- 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.
- Obserwuj tabelę: wiersz i kolumna bieżącego przystanku są zabarwione, a każdy krok wpisuje krótszą odległość.
- Wybierz start i cel, aby na końcu zobaczyć najkrótszą ścieżkę między nimi. Nowy graf tworzy inny graf do wypróbowania.
Jak działa algorytm Floyda–Warshalla
Zrób tabelę z jednym wierszem i jedną kolumną na każdy wierzchołek. Wpisz 0 na przekątnej, długość krawędzi tam, gdzie dwa wierzchołki są połączone, a wszędzie indziej nieskończoność. Potem bierz po kolei każdy wierzchołek k jako możliwy przystanek. Dla każdej pary i, j porównaj odległość z i do j w tabeli z odległością z i do k plus odległością z k do j i zostaw mniejszą. Po ostatnim wierzchołku każda komórka to najkrótsza odległość między jej dwoma wierzchołkami.
Dlaczego to działa
Po rundzie dla k tabela zawiera dla każdej pary najkrótszą ścieżkę, której wszystkie przystanki należą do wierzchołków już rozpatrzonych. Runda dla następnego wierzchołka musi tylko rozstrzygnąć, czy on pomaga: najkrótsza ścieżka przez niego to najkrótsza ścieżka do niego plus najkrótsza ścieżka od niego, a obie są już w tabeli. Takie budowanie dużej odpowiedzi z mniejszych, już znalezionych, nazywa się programowaniem dynamicznym. Przy ujemnych krawędziach nadal działa, a liczba ujemna na przekątnej zdradza cykl ujemny.
Często zadawane pytania
Czym jest algorytm Floyda–Warshalla?
To algorytm, który znajduje najkrótszą odległość między każdą parą wierzchołków w grafie ważonym. Prowadzi tabelę odległości i dla każdego wierzchołka po kolei sprawdza, czy droga przez niego skraca którąś parę.
Jak szybki jest algorytm Floyda–Warshalla?
Ma trzy zagnieżdżone pętle po n wierzchołkach, więc praca rośnie jak n³, a tabela potrzebuje n² komórek. To wystarczy dla grafów z kilkuset wierzchołkami. Dla dużych rzadkich grafów szybciej jest uruchomić algorytm Dijkstry z każdego wierzchołka.
Czy algorytm Floyda–Warshalla radzi sobie z ujemnymi krawędziami?
Tak, o ile nie ma cyklu ujemnego. Jeśli jest, któraś komórka na przekątnej staje się ujemna i właśnie tak algorytm go wykrywa.
Jak uzyskać ścieżki, a nie tylko odległości?
Prowadź drugą tabelę z następnym wierzchołkiem na drodze z i do j. Za każdym razem, gdy para skraca się przez k, przepisz następny wierzchołek z i w stronę k. Idąc po tej tabeli od i do j, odczytasz ścieżkę.
Czy mój graf jest gdzieś wysyłany?
Nie. Graf powstaje i tabela jest wypełniana 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