Algorytm Floyda–Warshalla
Stare atlasy samochodowe miały na końcu tabelę: odległość między każdą parą miast. Algorytm Floyda–Warshalla to sposób na obliczenie takiej tabeli i jeden z najkrótszych algorytmów, jakie kiedykolwiek napisano: trzy pętle, jedno porównanie i każda najkrótsza odległość trafia na swoje miejsce.
Idea
Algorytm Dijkstry i algorytm Bellmana–Forda znajdują najkrótsze odległości od jednego startu. Algorytm Floyda–Warshalla znajduje je naraz z każdego wierzchołka do każdego innego, w tabeli z wierszem i kolumną na każdy wierzchołek. Zaczyna od tego, co bezpośrednio mówią krawędzie, a potem poprawia całą tabelę, dopuszczając coraz więcej wierzchołków jako przystanki po drodze.
Krok po kroku
Wypełnij tabelę: 0 z każdego wierzchołka do niego samego, długość krawędzi między sąsiadami i nieskończoność w pozostałych miejscach. Potem dla każdego wierzchołka k i każdej pary i, j: jeśli odległość z i do k plus odległość z k do j jest mniejsza niż odległość z i do j, wpisz mniejszą liczbę. To cały algorytm. W kodzie to trzy pętle, z k na zewnątrz.
Przykład
Weźmy cztery wierzchołki i krawędzie A–B o długości 3, B–C 1, A–C 5 i C–D 2. Tabela zaczyna od nich i od nieskończoności dla A–D i B–D. Runda A nic nie zmienia, bo każda droga przez A jest dłuższa. Runda B znajduje drogę z A do C przez B: 3 + 1 = 4, mniej niż 5. Runda C znajduje drogę z A do D przez C: 4 + 2 = 6, oraz z B do D: 1 + 2 = 3, obie jako pierwsze znalezione. Runda D nic nie zmienia. Końcowa tabela: A–B 3, A–C 4, A–D 6, B–C 1, B–D 3, C–D 2.
Dlaczego kolejność pętli ma znaczenie
Przystanek k musi być w zewnętrznej pętli. Po rundzie dla k każda komórka to najkrótsza odległość, w której przystankami mogą być tylko wierzchołki spośród pierwszych k, a następna runda na tym buduje: najlepsza ścieżka przez nowy przystanek to najlepsza ścieżka do niego plus najlepsza ścieżka od niego, a obie są już poprawne. Umieszczenie k w pętli wewnętrznej łamie tę gwarancję i może zostawić błędne odległości. Aktualizowanie tabeli w miejscu w trakcie rundy jest bezpieczne, bo wiersz i kolumna samego k w tej rundzie się nie zmieniają.
Historia i zastosowania
Bernard Roy opisał tę metodę w 1959 roku. W 1962 roku Stephen Warshall opublikował ją dla domknięcia przechodniego, które pyta tylko, czy jeden wierzchołek może dotrzeć do drugiego, a Robert Floyd – dla najkrótszych ścieżek. Metoda oblicza tabele odległości i tablice routingu, znajduje średnicę sieci, mówi, które wierzchołki mogą dotrzeć do których, a ujemna komórka na przekątnej zdradza cykl ujemny.
Wypróbuj
Otwórz aplikację i naciśnij Krok. Graf jest po jednej stronie, a tabela po drugiej. Każda runda wyróżnia wiersz i kolumnę bieżącego przystanku; każdy krok wpisuje krótszą odległość jednej pary i obrysowuje dwie komórki, które zostały dodane. Komórki zmienione w tej rundzie są zabarwione. Wybierz start i cel, aby zobaczyć najkrótszą ścieżkę między nimi, gdy tabela będzie gotowa.
Często zadawane pytania
Jaka jest złożoność czasowa algorytmu Floyda–Warshalla?
O(n³) dla n wierzchołków, niezależnie od liczby krawędzi, i O(n²) pamięci na tabelę. To metoda z wyboru dla małych lub gęstych grafów, w których jego prosta pętla działa bardzo szybko.
Floyd–Warshall czy Dijkstra z każdego wierzchołka?
Dla gęstego grafu albo gdy krawędzie mogą być ujemne algorytm Floyda–Warshalla jest prostszy i mniej więcej tak samo szybki. Dla dużego rzadkiego grafu bez ujemnych krawędzi szybciej jest uruchomić algorytm Dijkstry z każdego wierzchołka.
Czy algorytm Floyda–Warshalla to programowanie dynamiczne?
Tak. Rozwiązuje problem dla ścieżek z przystankami wśród pierwszych k wierzchołków, korzystając z odpowiedzi dla pierwszych k − 1 wierzchołków, i trzyma tylko jedną tabelę, którą na bieżąco nadpisuje.
Czym jest domknięcie przechodnie?
To tabela tego, które wierzchołki mogą dotrzeć do których, bez odległości. Wersja algorytmu według Warshalla oblicza ją za pomocą "lub" i "i" zamiast "min" i "+".
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Wypróbuj algorytm Floyda–Warshalla