Floyd-Warshallův algoritmus

V tomto kurzu se dozvíte, jak funguje algoritmus floyd-warshall. Najdete také funkční příklady algoritmu floyd-warshall v jazycích C, C ++, Java a Python.

Floyd-Warshall Algorithm je algoritmus pro nalezení nejkratší cesty mezi všemi dvojicemi vrcholů ve váženém grafu. Tento algoritmus funguje pro směrované i neorientované vážené grafy. Nepracuje však pro grafy se zápornými cykly (kde je součet hran v cyklu záporný).

Vážený graf je graf, ve kterém má každá hrana přidruženou číselnou hodnotu.

Algoritmus Floyd-Warhshall se také nazývá Floydův algoritmus, Roy-Floydův algoritmus, Roy-Warshallův algoritmus nebo WFI algoritmus.

Tento algoritmus sleduje přístup dynamického programování k nalezení nejkratších cest.

Jak funguje Floyd-Warshallův algoritmus?

Nechť daný graf je:

Počáteční graf

Postupujte podle následujících pokynů a najděte nejkratší cestu mezi všemi dvojicemi vrcholů.

  1. Vytvořte matici dimenze, kde n je počet vrcholů. Řádek a sloupec jsou indexovány jako i, respektive j. i a j jsou vrcholy grafu. Každá buňka A (i) (j) je vyplněna vzdáleností od vrcholu k vrcholu. Pokud neexistuje žádná cesta od vrcholu k vrcholu, je buňka ponechána jako nekonečno. Naplňte každou buňku vzdáleností mezi i-tým a j-tým vrcholemA0n*n
    ithjthithjth
  2. Nyní vytvořte matici pomocí matice . Prvky v prvním sloupci a prvním řádku jsou ponechány tak, jak jsou. Zbývající buňky jsou vyplněny následujícím způsobem. Nechť k je mezilehlý vrchol v nejkratší cestě od zdroje k cíli. V tomto kroku je k první vrchol. je naplněn . To znamená, že pokud je přímá vzdálenost od zdroje k cíli větší než cesta vrcholem k, pak je buňka vyplněna . V tomto kroku je k vrchol 1. Počítáme vzdálenost od zdrojového vrcholu k cílovému vrcholu přes tento vrchol k. Vypočítejte vzdálenost od zdrojového vrcholu k cílovému vrcholu přes tento vrchol k Například: ProA1A0
    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), přímá vzdálenost od vrcholu 2 k 4 je 4 a součet vzdálenosti od vrcholu 2 k 4 přes vrchol (tj. od vrcholu 2 k 1 a od vrcholu 1 k 4) je 7. Protože 4 < 7, je vyplněn 4.A0(2, 4)
  3. Podobně se vytváří pomocí . Prvky ve druhém sloupci a druhém řádku jsou ponechány tak, jak jsou. V tomto kroku je k druhým vrcholem (tj. Vrcholem 2). Zbývající kroky jsou stejné jako v kroku 2 . Vypočítejte vzdálenost od zdrojového vrcholu k cílovému vrcholu přes tento vrchol 2A2A3
  4. Podobně, a je také vytvořen. Vypočítejte vzdálenost od zdrojového vrcholu k cílovému vrcholu přes tento vrchol 3 Vypočítejte vzdálenost od zdrojového vrcholu k cílovému vrcholu přes tento vrchol 4A3A4
  5. A4 dává nejkratší cestu mezi každou dvojicí vrcholů.

Floyd-Warshallův algoritmus

n = počet vrcholů A = matice dimenze n * n pro k = 1 až n pro i = 1 až n pro j = 1 až n A k (i, j) = min (A k-1 (i, j) , A k-1 (i, k) + A k-1 (k, j)) návrat A

Python, Java a C / C ++ příklady

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); )

Složitost algoritmu Floyd Warshall

Časová složitost

K dispozici jsou tři smyčky. Každá smyčka má neustálé složitosti. Časová složitost algoritmu Floyd-Warshall tedy je .O(n3)

Složitost vesmíru

Složitost prostoru algoritmu Floyd-Warshall je .O(n2)

Aplikace Floyd Warshall Algorithm

  • Chcete-li najít nejkratší cestu, je směrovaný graf
  • Najít přechodné uzavření směrovaných grafů
  • Najít inverzi skutečných matic
  • Pro testování, zda je neorientovaný graf bipartitní

Zajímavé články...