Algorytm Floyda-Warshalla

Tutorial
Na ten temat mamy również tutorial „Algorytm Floyda-Warshalla”, który ilustruje działanie algorytmu krok po kroku. Zapraszamy do zapoznania się z nim!

Algorytm Floyda-Warshalla – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Jest to algorytm oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n3) i złożoność pamięciową O(n2), gdzie n jest liczbą wierzchołków.

Algorytm dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli. Algorytm może być również wykorzystywany do wyszukiwania ujemnych cykli w grafie.

Działanie algorytmu

Tworzymy dwie macierze o wymiarach n na n. W pierwszej macierzy będziemy przechowywać odległości między punktami, w drugiej identyfikatory przedostatnich punktów na ścieżce łączącej punkty. Bardziej formalnie, wartość di,j oznacza odległość z punktu i do punktu j, a wartość pi,j oznacza punkt poprzedzający punkt j na ścieżce z punktu i do punktu j.

Na początku inicjujemy wartości w macierzach. Jeśli istnieje krawędź prowadząca z punktu i do punktu j, to wartości di,j przypisujemy długość tej krawędzi, a wartość pi,j ustawiamy na i. W przeciwnym razie wartości di,j przypisujemy nieskończoność, a wartość pi,j traktujemy jako niezdefiniowaną. Długości ścieżek prowadzących do tego samego punktu, z którego wychodzą, ustawiamy na 0.

Następnie wykonujemy zasadniczą część algorytmu:

  • Dla każdego punktu u ze zbioru wierzchołków:
    • Dla każdego punktu v1 ze zbioru wierzchołków:
      • Dla każdego punktu v2 ze zbioru wierzchołków:
        • Jeśli dv1, v2 > dv1, u + du, v2, to:
          • dv1, v2 = dv1, u + du, v2,
          • pv1, v2 = pu, v2.

Po wykonaniu algorytmu macierze zawierają optymalne rozwiązania. Ścieżkę między dwoma dowolnymi punktami można odczytać wykorzystując wartości znajdujące się w macierzy p. Jeśli po wykonaniu algorytmu wartość di,j nadal wynosi nieskończoność, to oznacza, że nie istnieje żadna ścieżka prowadząca z punktu i do punktu j.

Jeśli po wykonaniu algorytmu na głównej przekątnej macierzy odległości znajduje się wartość mniejsza od zera, to graf zawiera ujemny cykl.

Złożoność obliczeniowa

Algorytm zawiera trzy zagnieżdżone pętle, w każdej z nich przeglądane są wszystkie wierzchołki. Złożoność czasowa algorytmu wynosi zatem O(n3) (n jest liczbą wierzchołków). Dane są przechowywane w dwóch macierzach o wymiarach n na n. Złożoność pamięciowa algorytmu wynosi zatem O(n2).

Dodano: 9 sierpnia 2017 13:51
Ostatnia edycja: 10 sierpnia 2017 15:02