Floyd-Warshall algoritmus

Ebben az oktatóanyagban megtudhatja, hogyan működik a floyd-warshall algoritmus. A Floyd-warshall algoritmusra működő példákat is talál a C, C ++, Java és Python nyelven.

A Floyd-Warshall algoritmus olyan algoritmus, amely egy súlyozott gráfban megtalálja a legrövidebb utat az összes csúcspár között. Ez az algoritmus mind az irányított, mind a nem irányított súlyozott grafikonok esetében működik. De ez nem működik a negatív ciklusú grafikonok esetében (ahol a ciklus éleinek összege negatív).

A súlyozott gráf olyan gráf, amelyben az egyes élekhez számérték tartozik.

A Floyd-Warhshall algoritmust Floyd algoritmusának, Roy-Floyd algoritmusának, Roy-Warshall algoritmusának vagy WFI algoritmusának is nevezik.

Ez az algoritmus a dinamikus programozási megközelítést követi a legrövidebb utak megtalálásához.

Hogyan működik a Floyd-Warshall algoritmus?

Legyen az adott grafikon:

Kezdeti grafikon

Kövesse az alábbi lépéseket, hogy megtalálja a legrövidebb utat az összes csúcspár között.

  1. Hozzon létre egy dimenziós mátrixot , ahol n a csúcsok száma. A sort és az oszlopot i, illetve j indexként indexelik. i és j a gráf csúcsai. Minden A (i) (j) cella kitölti a csúcs és a csúcs közötti távolságot . Ha nincs csúcsról csúcsra vezető út , akkor a cella végtelen marad. Töltsön meg minden cellát az i-edik és a j-es csúcs közötti távolsággalA0n*n
    ithjthithjth
  2. Most hozzon létre egy mátrixot a mátrix segítségével . Az első oszlop és az első sor elemei úgy maradnak, ahogy vannak. A fennmaradó cellákat a következő módon töltjük ki. Legyen k a köztes csúcs a legrövidebb úton a forrástól a célig. Ebben a lépésben k az első csúcs. tele van . Vagyis, ha a forrás és a cél közötti közvetlen távolság nagyobb, mint a k csúcson át vezető út, akkor a cella megtelt . Ebben a lépésben k az 1. csúcs. Kiszámoljuk a forrás csúcs és a cél csúcs közötti távolságot ezen a k csúcson keresztül. Számítsa ki a forrás csúcs és a cél csúcs közötti távolságot ezen a csúcson keresztül k Például: AA1A0
    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), a 2-től 4-ig terjedő közvetlen távolság 4, és a 2-től 4-ig terjedő csúcson (azaz a 2-től 1-ig és 1-től 4-ig) a távolság összege 7. Mivel 4 < 7, 4-tel van kitöltve.A0(2, 4)
  3. Ehhez hasonlóan jön létre . A második oszlop és a második sor elemei úgy maradnak, ahogy vannak. Ebben a lépésben k a második csúcs (azaz a 2. csúcs). A fennmaradó lépések megegyeznek a 2. lépésben leírtakkal . Számítsa ki a forrás csúcs és a cél csúcs közötti távolságot ezen a 2 csúcson keresztülA2A3
  4. Hasonlóképpen, és létre is jön. Számítsa ki a forráscsúcs és a célcsúcs közötti távolságot ezen a csúcson keresztül 3 Számítsa ki a forráscsúcs és a célcsúcs közötti távolságot ezen a csúcson keresztül 4A3A4
  5. A4 megadja a legrövidebb utat az egyes csúcspárok között.

Floyd-Warshall algoritmus

n = csúcsok száma A = n * n dimenzió mátrixa k = 1-től n-ig i = 1-től n-ig j = 1-től n-ig A k (i, j) = min (A k-1 (i, j) , A k-1 (i, k) + A k-1 (k, j)) visszatér A-val

Példák Python, Java és 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); )

Floyd Warshall algoritmus komplexitás

Az idő komplexitása

Három hurok van. Minden hurok állandóan összetett. Tehát a Floyd-Warshall algoritmus időbeli összetettsége .O(n3)

Tér komplexitás

A Floyd-Warshall algoritmus térbeli összetettsége az .O(n2)

Floyd Warshall algoritmus alkalmazások

  • A legrövidebb út megtalálásához egy irányított gráf szolgál
  • Megtalálni az irányított gráfok tranzitív lezárását
  • Megtalálni a valós mátrixok inverzióját
  • Annak tesztelésére, hogy egy irányítatlan gráf kétoldalas-e

érdekes cikkek...