algorithm
Algorytm Floyda-Warshalla

Algorytm najkrótszej ścieżki dla wszystkich par

Algorytm Floyda-Warshalla służy do znajdowania najkrótszych ścieżek na wykresie ważonym z dodatnimi lub ujemnymi wagami krawędzi. Pojedyncze wykonanie algorytmu znajdzie długości (zsumowane wagi) najkrótszych ścieżek między wszystkimi parami wierzchołków. Przy niewielkiej zmienności może wydrukować najkrótszą ścieżkę i wykryć cykle ujemne na wykresie. Floyd-Warshall to algorytm programowania dynamicznego.

Spójrzmy na przykład. Na tym wykresie zastosujemy algorytm Floyda-Warshalla:

Po pierwsze, bierzemy dwie matryce 2D. Są to macierze przylegania . Rozmiar macierzy będzie całkowitą liczbą wierzchołków. Do naszego wykresu weźmiemy macierze 4 * 4 . Macierz odległości będzie przechowywać minimalną odległość znalezioną do tej pory między dwoma wierzchołkami. Na początku, dla krawędzi, jeśli istnieje krawędź między UV a odległość / waga wynosi w , będziemy przechowywać: distance[u][v] = w . Dla wszystkich krawędzi, które nie istnieją, wprowadzimy nieskończoność . Matryca ścieżek służy do regeneracji ścieżki minimalnej odległości między dwoma wierzchołkami. Tak więc początkowo, jeśli istnieje ścieżka między u i v , wstawimy path[u][v] = u . Oznacza to, że najlepszym sposobem, aby przyjść do wierzchołka-v od wierzchołka-u jest użycie krawędzi łączącej V z u. Jeśli między dwoma wierzchołkami nie ma ścieżki, umieścimy tam N , wskazując, że nie ma obecnie dostępnej ścieżki. Dwie tabele dla naszego wykresu będą wyglądały następująco:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  6  |  15 |            |  1  |  N  |  1  |  1  |  1  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  | inf |  0  | -2  | inf |            |  2  |  N  |  N  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  | inf | inf |  0  |  2  |            |  3  |  N  |  N  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  | inf | inf |  0  |            |  4  |  4  |  N  |  N  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

Ponieważ nie ma pętli, przekątne są ustawione na N. Odległość od samego wierzchołka wynosi 0 .

Aby zastosować algorytm Floyda-Warshalla, wybierzemy środkowy wierzchołek k . Następnie dla każdego wierzchołka i sprawdzimy, czy możemy przejść od i do k, a następnie od k do j , gdzie j jest innym wierzchołkiem i zminimalizujemy koszty przejścia od i do j . Jeśli bieżąca odległość [i] [j] jest większa niż odległość [i] [k] + odległość [k] [j] , ustawimy odległość [i] [j] równą sumie tych dwóch odległości . Ścieżka [i] [j] zostanie ustawiona na ścieżkę [k] [j] , ponieważ lepiej jest przejść od i do k , a następnie od k do j . Wszystkie wierzchołki zostaną wybrane jako k . Musimy 3 zagnieżdżone pętle: k trwającego od 1 do 4, i począwszy od 1 do 4 i j trwającego od 1 do 4. Jedziemy czek:

if distance[i][j] > distance[i][k] + distance[k][j]
    distance[i][j] := distance[i][k] + distance[k][j]
    path[i][j] := path[k][j]
end if

Więc w zasadzie sprawdzamy, czy dla każdej pary wierzchołków uzyskujemy krótszy dystans, przechodząc przez inny wierzchołek? Całkowita liczba operacji dla naszego wykresu wyniesie 4 * 4 * 4 = 64 . Oznacza to, że sprawdzimy to 64 razy. Spójrzmy na kilka z nich:

Gdy k = 1 , i = 2 i j = 3 , odległość [i] [j] wynosi -2 , co nie jest większe niż odległość [i] [k] + odległość [k] [j] = -2 + 0 = -2 . Więc pozostanie niezmieniony. Ponownie, gdy k = 1 , i = 4 i j = 2 , odległość [i] [j] = nieskończoność , która jest większa niż odległość [i] [k] + odległość [k] [j] = 1 + 3 = 4 . Więc umieszczamy odległość [i] [j] = 4 i umieszczamy ścieżkę [i] [j] = ścieżka [k] [j] = 1 . Oznacza to, że aby przejść z wierzchołka-4 do wierzchołka-2 , ścieżka 4-> 1-> 2 jest krótsza niż istniejąca ścieżka. W ten sposób wypełniamy obie macierze. Obliczenia dla każdego kroku pokazano tutaj . Po wprowadzeniu niezbędnych zmian nasze matryce będą wyglądały następująco:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  1  |  3  |            |  1  |  N  |  1  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  |  1  |  0  | -2  |  0  |            |  2  |  4  |  N  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  |  3  |  6  |  0  |  2  |            |  3  |  4  |  1  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  |  4  |  2  |  0  |            |  4  |  4  |  1  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

To nasza najkrótsza macierz odległości. Na przykład najkrótsza odległość od 1 do 4 wynosi 3, a najkrótsza odległość od 4 do 3 wynosi 2 . Nasz pseudo-kod będzie:

Procedure Floyd-Warshall(Graph):
for k from 1 to V     // V denotes the number of vertex
    for i from 1 to V
       for j from 1 to V
           if distance[i][j] > distance[i][k] + distance[k][j]
               distance[i][j] := distance[i][k] + distance[k][j]
               path[i][j] := path[k][j]
           end if
       end for
    end for
end for

Drukowanie ścieżki:

Aby wydrukować ścieżkę, sprawdzimy macierz Ścieżki . Aby wydrukować ścieżkę od u do v , zaczniemy od ścieżki [u] [v] . Ustawimy zmienianie v = ścieżka [u] [v], dopóki nie znajdziemy ścieżki [u] [v] = u i nie wypchniemy wszystkich wartości ścieżki [u] [v] na stos. Po znalezieniu u, będziemy drukować u i zacząć popping elementy ze stosu i wydrukować je. Działa to, ponieważ macierz ścieżek przechowuje wartość wierzchołka, który dzieli najkrótszą ścieżkę do v z dowolnego innego węzła. Pseudo-kod będzie:

Procedure PrintPath(source, destination):
s = Stack()
S.push(destination)
while Path[source][destination] is not equal to source
    S.push(Path[source][destination])
    destination := Path[source][destination]
end while
print -> source
while S is not empty
    print -> S.pop
end while

Znajdowanie cyklu ujemnej krawędzi:

Aby dowiedzieć się, czy istnieje ujemny cykl zbocza, musimy sprawdzić główną przekątną macierzy odległości . Jeśli jakakolwiek wartość na przekątnej jest ujemna, oznacza to, że na wykresie występuje cykl ujemny.

Złożoność:

Złożoność algorytmu Floyda-Warshalla wynosi O (V³), a złożoność przestrzeni to: O (V²) .