Algorytm Floyda-Warshalla

W tym samouczku dowiesz się, jak działa algorytm Floyd-warshall. Znajdziesz również działające przykłady algorytmu floyd-warshall w językach C, C ++, Java i Python.

Algorytm Floyda-Warshalla to algorytm znajdowania najkrótszej ścieżki między wszystkimi parami wierzchołków na grafie ważonym. Ten algorytm działa zarówno dla grafów ważonych skierowanych, jak i niekierunkowych. Ale to nie działa dla wykresów z cyklami ujemnymi (gdzie suma krawędzi w cyklu jest ujemna).

Wykres ważony to wykres, na którym każda krawędź ma przypisaną wartość liczbową.

Algorytm Floyda-Warhshalla jest również nazywany algorytmem Floyda, algorytmem Roya-Floyda, algorytmem Roya-Warshalla lub algorytmem WFI.

Ten algorytm jest zgodny z podejściem programowania dynamicznego, aby znaleźć najkrótsze ścieżki.

Jak działa algorytm Floyda-Warshalla?

Niech dany wykres będzie:

Wykres początkowy

Wykonaj poniższe czynności, aby znaleźć najkrótszą ścieżkę między wszystkimi parami wierzchołków.

  1. Utwórz macierz wymiarów, gdzie n to liczba wierzchołków. Wiersz i kolumna są indeksowane odpowiednio jako i i j. i i j są wierzchołkami wykresu. Każda komórka A (i) (j) jest wypełniona odległością od wierzchołka do wierzchołka. Jeśli nie ma ścieżki od wierzchołka do wierzchołka, komórka pozostaje w nieskończoności. Wypełnij każdą komórkę odległością między i-tym a j-tym wierzchołkiemA0n*n
    ithjthithjth
  2. Teraz utwórz macierz za pomocą macierzy . Elementy w pierwszej kolumnie i pierwszym wierszu pozostają niezmienione. Pozostałe komórki są wypełniane w następujący sposób. Niech k będzie pośrednim wierzchołkiem na najkrótszej ścieżce od źródła do celu. Na tym etapie k jest pierwszym wierzchołkiem. jest wypełniony . Oznacza to, że jeśli bezpośrednia odległość od źródła do celu jest większa niż ścieżka przez wierzchołek k, to komórka jest wypełniona . W tym kroku k jest wierzchołkiem 1. Obliczamy odległość od wierzchołka źródłowego do wierzchołka docelowego przez ten wierzchołek k. Oblicz odległość od wierzchołka źródłowego do wierzchołka docelowego przez ten wierzchołek k Na przykład: ForA1A0
    A(i)(j)(A(i)(k) + A(k)(j)) if (A(i)(j)> A(i)(k) + A(k)(j))
    A(i)(k) + A(k)(j)

    A1(2, 4), Bezpośrednią odległość od wierzchołka 2 do 4. 4, a suma odległości od wierzchołka 2 do 4 do wierzchołka (tzn. Od wierzchołka 2 do 1, a z wierzchołka od 1 do 4), 7. Ponieważ 4 < 7, jest wypełniona 4.A0(2, 4)
  3. Podobnie jest tworzony za pomocą . Elementy w drugiej kolumnie i drugim wierszu pozostają niezmienione. Na tym etapie k jest drugim wierzchołkiem (tj. Wierzchołkiem 2). Pozostałe kroki są takie same, jak w kroku 2 . Oblicz odległość od wierzchołka źródłowego do wierzchołka docelowego przez ten wierzchołek 2A2A3
  4. Podobnie i jest również tworzony. Oblicz odległość od wierzchołka źródłowego do docelowego przez ten wierzchołek 3 Oblicz odległość od źródłowego wierzchołka do docelowego wierzchołka przez ten wierzchołek 4A3A4
  5. A4 podaje najkrótszą ścieżkę między każdą parą wierzchołków.

Algorytm Floyda-Warshalla

n = liczba wierzchołków A = macierz wymiaru n * n dla k = 1 do n dla i = 1 do n dla j = 1 do n A k (i, j) = min (A k-1 (i, j) , A k-1 (i, k) + A k-1 (k, j)) powrót A

Przykłady w Pythonie, Javie i C / C ++

Python Java C C ++ 
 # Floyd Warshall Algorithm in python # The number of vertices nV = 4 INF = 999 # Algorithm implementation def floyd_warshall(G): distance = list(map(lambda i: list(map(lambda j: j, i)), G)) # Adding vertices individually for k in range(nV): for i in range(nV): for j in range(nV): distance(i)(j) = min(distance(i)(j), distance(i)(k) + distance(k)(j)) print_solution(distance) # Printing the solution def print_solution(distance): for i in range(nV): for j in range(nV): if(distance(i)(j) == INF): print("INF", end=" ") else: print(distance(i)(j), end=" ") print(" ") G = ((0, 3, INF, 5), (2, 0, INF, 4), (INF, 1, 0, INF), (INF, INF, 2, 0)) floyd_warshall(G)
 // Floyd Warshall Algorithm in Java class FloydWarshall ( final static int INF = 9999, nV = 4; // Implementing floyd warshall algorithm void floydWarshall(int graph()()) ( int matrix()() = new int(nV)(nV); int i, j, k; for (i = 0; i < nV; i++) for (j = 0; j < nV; j++) matrix(i)(j) = graph(i)(j); // Adding vertices individually for (k = 0; k < nV; k++) ( for (i = 0; i < nV; i++) ( for (j = 0; j < nV; j++) ( if (matrix(i)(k) + matrix(k)(j) < matrix(i)(j)) matrix(i)(j) = matrix(i)(k) + matrix(k)(j); ) ) ) printMatrix(matrix); ) void printMatrix(int matrix()()) ( for (int i = 0; i < nV; ++i) ( for (int j = 0; j < nV; ++j) ( if (matrix(i)(j) == INF) System.out.print("INF "); else System.out.print(matrix(i)(j) + " "); ) System.out.println(); ) ) public static void main(String() args) ( int graph()() = ( ( 0, 3, INF, 5 ), ( 2, 0, INF, 4 ), ( INF, 1, 0, INF ), ( INF, INF, 2, 0 ) ); FloydWarshall a = new FloydWarshall(); a.floydWarshall(graph); ) )
 // Floyd-Warshall Algorithm in C #include // defining the number of vertices #define nV 4 #define INF 999 void printMatrix(int matrix()(nV)); // Implementing floyd warshall algorithm void floydWarshall(int graph()(nV)) ( int matrix(nV)(nV), i, j, k; for (i = 0; i < nV; i++) for (j = 0; j < nV; j++) matrix(i)(j) = graph(i)(j); // Adding vertices individually for (k = 0; k < nV; k++) ( for (i = 0; i < nV; i++) ( for (j = 0; j < nV; j++) ( if (matrix(i)(k) + matrix(k)(j) < matrix(i)(j)) matrix(i)(j) = matrix(i)(k) + matrix(k)(j); ) ) ) printMatrix(matrix); ) void printMatrix(int matrix()(nV)) ( for (int i = 0; i < nV; i++) ( for (int j = 0; j < nV; j++) ( if (matrix(i)(j) == INF) printf("%4s", "INF"); else printf("%4d", matrix(i)(j)); ) printf(""); ) ) int main() ( int graph(nV)(nV) = ((0, 3, INF, 5), (2, 0, INF, 4), (INF, 1, 0, INF), (INF, INF, 2, 0)); floydWarshall(graph); )
 // Floyd-Warshall Algorithm in C++ #include using namespace std; // defining the number of vertices #define nV 4 #define INF 999 void printMatrix(int matrix()(nV)); // Implementing floyd warshall algorithm void floydWarshall(int graph()(nV)) ( int matrix(nV)(nV), i, j, k; for (i = 0; i < nV; i++) for (j = 0; j < nV; j++) matrix(i)(j) = graph(i)(j); // Adding vertices individually for (k = 0; k < nV; k++) ( for (i = 0; i < nV; i++) ( for (j = 0; j < nV; j++) ( if (matrix(i)(k) + matrix(k)(j) < matrix(i)(j)) matrix(i)(j) = matrix(i)(k) + matrix(k)(j); ) ) ) printMatrix(matrix); ) void printMatrix(int matrix()(nV)) ( for (int i = 0; i < nV; i++) ( for (int j = 0; j < nV; j++) ( if (matrix(i)(j) == INF) printf("%4s", "INF"); else printf("%4d", matrix(i)(j)); ) printf(""); ) ) int main() ( int graph(nV)(nV) = ((0, 3, INF, 5), (2, 0, INF, 4), (INF, 1, 0, INF), (INF, INF, 2, 0)); floydWarshall(graph); )

Złożoność algorytmu Floyda Warshalla

Złożoność czasowa

Istnieją trzy pętle. Każda pętla ma stałą złożoność. Zatem złożoność czasowa algorytmu Floyda-Warshalla wynosi .O(n3)

Złożoność przestrzeni

Przestrzenna złożoność algorytmu Floyda-Warshalla wynosi .O(n2)

Aplikacje algorytmów Floyd Warshall

  • Aby znaleźć najkrótszą ścieżkę, jest skierowany wykres
  • Aby znaleźć przechodnie domknięcie skierowanych grafów
  • Aby znaleźć odwrócenie rzeczywistych macierzy
  • Do sprawdzania, czy wykres nieukierunkowany jest dwudzielny

Interesujące artykuły...