Algorytm Floyda-Warshalla: Najkrótsze Ścieżki Między Wszyscy Wierzchami w O(V³)

Drogi jako zbiory dozwolonych wierzchołków pośrednich

Rozważając graf skierowany o ważonym n = |V| wierzchołkach, problem najkrótszego szlaku dla wszystkich par pyta o odległość d(i, j) między każdą parą. Robert Floyd i Stephen Warshall w 1962 roku znaleźli sztuczkę: zamiast myśleć o drogach przez długość, należy myśleć o nich poprzez to, jakie wierzchołki pośrednie mogą przebywać. Zdefiniuj dist[k][i][j] jako najkrótszą drogę z i do j używając tylko wierzchołków {1, …, k} jako przystanków pośrednich.

dist[0][i][j] = w(i,j) jeśli istnieje krawędź, 0 jeśli i=j, w przeciwnym razie ∞ dist[k][i][j] = min( dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j] ) Odpowiedź: dist[n][i][j] dla każdej pary Droga używająca {1..k} albo nigdy nie dotyka wierzchołka k (ta sama cena jak wcześniej) albo przechodzi przez niego dokładnie raz, dzieląc się na segment od i do k i od k do j. Ponieważ dist[k] zależy tylko od dist[k−1], cały 3D-owy macierz upada do jednej n×n-owej matrycy aktualizowanej w miejscu — trzy pętle powiązane, bez kolejki priorytetowej, bez rekurencji.

dist[0][i][j] = w(i,j) if edge exists, 0 if i=j, else ∞

dist[k][i][j] = min( dist[k-1][i][j],
                      dist[k-1][i][k] + dist[k-1][k][j] )

Answer: dist[n][i][j] for every pair

Poprawność, złożoność i pułapka kolejności pętli

Dowód stanowi czysty indukcyjny na k: zakładając, że dist[k−1] jest poprawne dla wszystkich i, j, każdy najkrótszy ścieżki ograniczony do {1..k} albo unika k (taka sama koszt), albo odwiedza go dokładnie raz — argument optymalnego podstruktury, który czyni rekurencję dokładną. Algorytm działa w czasie O(V³) i w przestrzeni O(V²) niezależnie od liczby krawędzi, co czyni go najlepszym wyborem na gęstych grafach, gdzie dorównuje lub przewyższa uruchamianie Dijkstrę V razy. Pętla k-owa musi być najzewnętrzną — rekurencja potrzebuje, aby dist[k−1] został w pełni zdefiniowane przed użyciem k jako nowego pośredniego punktu, a zamiana kolejności pętli bezgłośnie łamie poprawność.

Negatywne cykle pojawiają się niemal bez problemu

W przeciwieństwie do algorytmu Dijkstry, Floyd-Warshall z powodzeniem obsługuje wagi krawędzi ujemnych, o ile suma wag w jakimś cyklu nie jest mniejsza od zera. Po uruchomieniu algorytmu sprawdź przekątną: dist[i][i] zaczyna się od 0 i może stać się ujemne tylko wtedy, gdy jakiś cykl przechodzący przez wierzchołek i_ oraz posiadający ujemną sumę wag spełnia definicję negatywnego cyklu. To właśnie jest główny powód popularności algorytmu Floyd-Warshall nawet na grafach, gdzie istnieją szybsze metody: algorytm Johnsona (Bellman-Ford do ponownego przypisania wag w taki sposób, aby były nieujemne, a następnie Dijkstry z każdego wierzchołka) przewyższa Floyd-Warshalla w przypadku gęstościowych grafów z ujemnymi wagami, osiągając O(V²log V + VE), ale wymaga dodatkowej, jawnej pętli do wykonania tej samej kontroli.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz the simulation i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.