Floyd-Warshall dla wszystkich par

Czasami potrzebna jest najkrótsza ścieżka między każdą parą wierzchołków, a nie tylko ścieżki z jednego źródła. To problem najkrótszych ścieżek dla wszystkich par.

Floyd-Warshall wypełnia pełną tabelę odległości dla wszystkich par za pomocą trzech przejrzystych zagnieżdżonych pętli i niemal bez dodatkowej konfiguracji.

Należy użyć macierzy, w której dist[i][j] oznacza najlepiej znany koszt przejścia z i do j. Macierz należy zainicjalizować na podstawie podanych krawędzi bezpośrednich.

Każdy wierzchołek może dotrzeć do samego siebie bez kosztu, dlatego przed rozpoczęciem relaksacji należy ustawić przekątną dist[i][i] na zero.

Sztuczka polega na tym, aby zezwolić ścieżkom na przechodzenie przez pośredni wierzchołek k, a następnie sprawdzić, czy trasa przez k jest tańsza niż przejście bezpośrednie.

Pętla zewnętrzna to k, czyli wybrany punkt pośredni. Pętle wewnętrzne i oraz j sprawdzają każdą parę względem tego punktu.

Dla każdej pary należy wykonać relaksację przez k: jeśli przejście z i do k, a następnie z k do j jest krótsze, należy zaktualizować dist[i][j] połączonym kosztem.

Po zakończeniu przetwarzania k wszystkie pary mogą korzystać z wierzchołków pośrednich aż do k. Umieszczenie k na najbardziej zewnętrznej pętli zapewnia poprawność tej zasady.

Algorytm Floyda-Warshalla obsługuje ujemne krawędzie, ale nie ujemne cykle. Ujemny cykl powoduje, że pewna wartość na przekątnej staje się mniejsza od zera.

Trzy pętle przechodzące przez n wierzchołków dają czas O(n^3) i pamięć O(n^2), więc rozwiązanie jest praktyczne tylko wtedy, gdy n nie przekracza kilkuset.

Algorytm Floyda-Warshalla należy wybrać, gdy graf jest mały i gęsty oraz rzeczywiście potrzebne są odległości między każdą parą, a nie odległości z jednego źródła.

Należy zainicjalizować macierz, wyzerować przekątną, a następnie wykonać pętle k, i, j i relaksować ścieżki przez k. Najkrótsze ścieżki dla wszystkich par w czasie O(n^3). 🧮