🗺️ Floyd-Warshall — najkrótsze ścieżki między wszystkimi parami

Suwak Wierzchołki (5 do 7) ustawia, ile wierzchołków ma losowy graf, co ustala też rozmiar macierzy odległości i liczbę pivotów, przez które przechodzi algorytm. Prędkość (0,2 do 4) kontroluje, jak szybko Odtwórz automatycznie przechodzi przez kroki relaksacji; nie ma wpływu, gdy używasz Krok, który zawsze przesuwa się dokładnie o wartość relaksacji jednego pivotu na kliknięcie.

Odtwórz uruchamia algorytm w sposób ciągły z wybraną Prędkością, przechodząc przez i, j i ostatecznie pivot k, aż każdy pivot zostanie przetworzony, a przebieg oznaczony jako Zakończony. Krok natomiast przechodzi przez cały jeden pivot k za jednym kliknięciem, stosując od razu wszystkie jego relaksacje (i, j), co jest przydatne do zatrzymywania się i sprawdzania macierzy między pivotami.

Wybierasz wierzchołki Źródło i Cel z list rozwijanych. Po zakończeniu przebiegu symulacja odtwarza ścieżkę, podążając za macierzą kolejnego skoku od źródła aż do celu, i rysuje każdą krawędź na tej trasie na fioletowo na grafie, podczas gdy statystyka Odległość ścieżki pokazuje łączną wagę lub symbol nieskończoności, jeśli ścieżka nie istnieje.

Symbol nieskończoności oznacza, że między wierzchołkiem tego wiersza i kolumny nie znaleziono jeszcze żadnej ścieżki. Przekątna zawsze zaczyna się od 0, ponieważ każdy wierzchołek dociera do siebie samego kosztem zero. W miarę jak pivot k przechodzi przez relaksacje w panelu dziennika, wpisy nieskończoności zamieniają się w liczby skończone, gdy tylko k okazuje się użytecznym przystankiem pośrednim między dwoma wierzchołkami, które nie były bezpośrednio połączone.

Wygeneruj ponownie buduje nowy losowy graf skierowany: spójny pierścień, dzięki któremu każdy wierzchołek może dotrzeć do następnego, plus garstka dodatkowych losowych krawędzi o wagach od 1 do 9, więc kształt problemu zmienia się przy każdym uruchomieniu. Zmiana suwaka Wierzchołki również wyzwala pełną regenerację, ponieważ rozmiar macierzy i długość pierścienia zależą od liczby wierzchołków.

Floyd-Warshall oblicza jednocześnie najkrótszą ścieżkę między każdą parą wierzchołków w grafie ważonym. Zamiast uruchamiać algorytm jednoźródłowy z każdego wierzchołka, wypełnia macierz odległości V×V, gdzie dist[i][j] to długość najkrótszej ścieżki z i do j. Działa na grafach skierowanych lub nieskierowanych i obsługuje ujemne wagi krawędzi, o ile nie ma ujemnego cyklu.

Algorytm wykorzystuje potrójną pętlę z zewnętrznym pivotem k. Dla każdej pary (i, j) sprawdza, czy przejście z i do k, a następnie z k do j jest krótsze niż bieżące najlepsze rozwiązanie: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Gdy pivot przejdzie przez wszystkie wierzchołki, każda najkrótsza ścieżka wykorzystująca wyłącznie wierzchołki pośrednie z pełnego zbioru zostanie znaleziona.

Istnieją trzy zagnieżdżone pętle, każda przebiegająca przez wszystkie V wierzchołków: pivot k, źródło i oraz cel j. Daje to V × V × V = V³ kroków relaksacji, więc złożoność czasowa wynosi O(V³). Złożoność pamięciowa wynosi O(V²) dla macierzy odległości, plus kolejne O(V²), jeśli przechowuje się macierz poprzedników do odtwarzania ścieżek.

Po iteracji k, dist[i][j] przechowuje najkrótszą ścieżkę z i do j, której wolno przechodzić wyłącznie przez wierzchołki pośrednie ponumerowane 1..k. Ponieważ pivot k jest najbardziej zewnętrzną pętlą, w chwili użycia dist[i][k] i dist[k][j] te wartości uwzględniają już wszystkie wcześniejsze pivoty, więc rekurencja jest zawsze budowana na optymalnych podrozwiązaniach. To klasyczny niezmiennik programowania dynamicznego, który czyni algorytm poprawnym.

W przeciwieństwie do Dijkstry, Floyd-Warshall toleruje ujemne wagi krawędzi i wciąż zwraca poprawne najkrótsze ścieżki. Ujemny cykl oznacza jednak, że niektóre najkrótsze ścieżki są niezdefiniowane, ponieważ można w nieskończoność zapętlać się, by obniżać koszt. Ujemny cykl można wykryć po przebiegu: jeśli którykolwiek wpis na przekątnej dist[i][i] staje się ujemny, wierzchołek i leży na ujemnym cyklu. Ta symulacja wykorzystuje wyłącznie nieujemne wagi, by wyniki pozostały dobrze zdefiniowane.

Podczas inicjalizacji macierz kolejnego skoku next[i][j] jest ustawiana na j, gdy tylko istnieje bezpośrednia krawędź. Za każdym razem, gdy relaksacja przez pivot k poprawia dist[i][j], kopiujemy next[i][j] = next[i][k], zapisując, że najlepsza trasa zaczyna się teraz od skierowania w stronę k. Aby odtworzyć ścieżkę, podąża się za next[i][j] od źródła aż do celu, zbierając wierzchołki po drodze.

Dijkstra rozwiązuje problem najkrótszej ścieżki z jednego źródła i jest szybki na rzadkich grafach, ale wymaga nieujemnych wag i daje ścieżki tylko z jednego źródła. Uruchomienie Dijkstry z każdego wierzchołka kosztuje około O(V·E·log V) z kopcem, co bije Floyda-Warshalla na dużych rzadkich grafach. Floyd-Warshall, z jego płaskim kosztem O(V³) i niewielkimi czynnikami stałymi, jest prostszy do zaimplementowania i często wygrywa na małych lub gęstych grafach oraz gdy naprawdę potrzebne są wszystkie pary.

Bellman-Ford również jest algorytmem jednoźródłowym, ale podobnie jak Floyd-Warshall akceptuje ujemne krawędzie i potrafi wykryć ujemne cykle. Działa w O(V·E) na źródło. Jeśli potrzebujesz najkrótszych ścieżek z jednego punktu w grafie z ujemnymi krawędziami, Bellman-Ford jest naturalnym wyborem; jeśli potrzebujesz wszystkich par naraz, trzy zwięzłe pętle Floyda-Warshalla są zwykle łatwiejsze i konkurencyjne na gęstych grafach.

Wpis ∞ oznacza, że obecnie nie ma znanej ścieżki między tymi dwoma wierzchołkami. Przekątna dist[i][i] zaczyna się od 0, ponieważ odległość od wierzchołka do samego siebie wynosi zero. W miarę postępu pivotu wpisy ∞ mogą stać się skończone, gdy wierzchołek pośredni łączy dwa wcześniej rozłączone węzły, co jest dokładnie tym „zaciskaniem się” macierzy widocznym w animacji.

Jest używany do tabel trasowania w małych sieciach, obliczania domknięcia przechodniego relacji, znajdowania średnicy i centralności grafu oraz rozwiązywania zapytań o odległości między wszystkimi parami w mapach, grach i badaniach operacyjnych. Wariant boolowski oblicza osiągalność, a wariant max-min rozwiązuje problemy najszerszej ścieżki lub wąskiego gardła, zamieniając operacje min/plus na max/min.