Floyd-Warshallov algoritem

V tej vadnici boste izvedeli, kako deluje algoritem floyd-warshall. Prav tako boste našli delovne primere algoritma floyd-warshall v jezikih C, C ++, Java in Python.

Algoritem Floyd-Warshall je algoritem za iskanje najkrajše poti med vsemi pari točk v tehtanem grafu. Ta algoritem deluje tako za usmerjene kot za neusmerjene tehtane grafe. Ne deluje pa za grafe z negativnimi cikli (kjer je vsota robov v ciklu negativna).

Uteženi graf je graf, v katerem je z vsakim robom povezana številčna vrednost.

Floyd-Warhshall algoritem se imenuje tudi Floydov algoritem, Roy-Floydov algoritem, Roy-Warshall algoritem ali WFI algoritem.

Ta algoritem sledi pristopu dinamičnega programiranja za iskanje najkrajših poti.

Kako deluje Floyd-Warshall Algorithm?

Naj bo dani graf:

Začetni graf

Sledite spodnjim korakom in poiščite najkrajšo pot med vsemi pari točk.

  1. Ustvari matriko dimenzij, kjer je n število točk. Vrstica in stolpec sta indeksirana kot i oziroma j. i in j sta točki grafa. Vsaka celica A (i) (j) je napolnjena z razdaljo od oglišča do oglišča. Če od vrha do vrha ni poti , ostane celica neskončna. Vsako celico napolnite z razdaljo med i in j točkoA0n*n
    ithjthithjth
  2. Zdaj ustvarite matriko z uporabo matrike . Elementi v prvem stolpcu in prvi vrstici ostanejo takšni, kot so. Preostale celice se zapolnijo na naslednji način. Naj bo k vmesna točka na najkrajši poti od vira do cilja. V tem koraku je k prva točka. je napolnjena z . To pomeni, da če je neposredna razdalja od vira do cilja večja od poti skozi točko k, je celica napolnjena z . V tem koraku je k točka 1. Izračunamo razdaljo od izhodiščne do ciljne točke skozi to točko k. Izračunajte razdaljo od izvorne točke do ciljne točke skozi to točko k Na primer: ZaA1A0
    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)Je zračna razdalja od tocke 2 do 4 je 4 in vsota razdalje od tocke 2 do 4 do tocke (tj. Od tocke 2 do 1 in od tocke 1 do 4) je 7. Ker 4 < 7, se napolni s 4.A0(2, 4)
  3. Podobno je ustvarjen z uporabo . Elementi v drugem stolpcu in drugi vrstici ostanejo takšni, kot so. V tem koraku je k druga točka (tj. Točka 2). Preostali koraki so enaki kot v 2. koraku . Izračunajte razdaljo od izvorne točke do ciljne točke skozi to točko 2A2A3
  4. Podobno, in je tudi ustvaril. Izračunaj razdaljo od izvorne točke do ciljne točke skozi to točko 3 Izračunaj razdaljo od izvorne točke do ciljne točke skozi to točko 4A3A4
  5. A4 poda najkrajšo pot med posameznimi pari točk.

Floyd-Warshallov algoritem

n = število točk A = matrika dimenzije n * n za k = 1 do n za i = 1 do n za j = 1 do n A k (i, j) = min (A k-1 (i, j) , A k-1 (i, k) + A k-1 (k, j)) vrne A

Primeri Python, Java in 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); )

Zapletenost algoritma Floyd Warshall

Zapletenost časa

Obstajajo tri zanke. Vsaka zanka ima nenehne zapletenosti. Torej, časovna zapletenost algoritma Floyd-Warshall je .O(n3)

Zapletenost prostora

Prostorska zapletenost algoritma Floyd-Warshall je .O(n2)

Aplikacije algoritma Floyd Warshall

  • Najti najkrajšo pot je usmerjen graf
  • Najti prehodno zapiranje usmerjenih grafov
  • Da bi našli inverzijo realnih matrik
  • Za preskušanje, ali je neusmerjeni graf dvostranski

Zanimive Članki...