Floyd-Warshalli algoritm

Selles õpetuses saate teada, kuidas floyd-warsi algoritm töötab. Samuti leiate toimivaid näiteid floyd-warsi algoritmidest C, C ++, Java ja Python.

Floyd-Warshalli algoritm on algoritm kaalutud graafil kõigi tipupaaride vahel lühima tee leidmiseks. See algoritm töötab nii suunatud kui ka suunamata kaalutud graafide puhul. Kuid see ei toimi negatiivsete tsüklitega graafikute puhul (kus tsükli servade summa on negatiivne).

Kaalutud graaf on graafik, milles igal serval on seotud arvuline väärtus.

Floyd-Warhshalli algoritmi nimetatakse ka Floydi algoritmiks, Roy-Floydi algoritmiks, Roy-Warshalli algoritmiks või WFI algoritmiks.

See algoritm järgib dünaamilise programmeerimise lähenemisviisi, et leida kõige lühemad teed.

Kuidas Floyd-Warshalli algoritm töötab?

Olgu antud graafik järgmine:

Esialgne graafik

Kõigi tippude paaride vahel lühima tee leidmiseks toimige järgmiselt.

  1. Loo mõõtmete maatriks , kus n on tippude arv. Rida ja veerg indekseeritakse vastavalt tähtedega i ja j. i ja j on graafi tipud. Iga lahter A (i) (j) on täidetud tipu ja tipu kaugusega . Kui tipust tippu ei ole teed , jääb lahter lõpmatuks. Täitke iga lahter i ja j tipu vahelise kaugusegaA0n*n
    ithjthithjth
  2. Nüüd looge maatriks maatriksi abil . Esimese veeru ja esimese rea elemendid jäetakse sellistena, nagu nad on. Ülejäänud lahtrid täidetakse järgmisel viisil. Olgu k lühima tee lähtekohast sihtpunktini vahetipp. Selles etapis on k esimene tipp. on täidetud . See tähendab, et kui otsene kaugus allikast sihtpunktini on suurem kui tippu k läbiv tee, siis lahter täidetakse . Selles etapis on k tipp 1. Arvutame selle tipu k kaudu kauguse lähtetippust sihttippuni. Arvutage selle tipu kaudu kaugus lähtetippust sihttippuni k Näiteks:A1A0
    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), otsene kaugus tipust 2 kuni 4 on 4 ja tipust 2 kuni 4 läbi tippu (st tipust 2 kuni 1 ja tipust 1 kuni 4) kauguse summa on 7. Kuna 4 < 7, on täidetud 4-ga.A0(2, 4)
  3. Samamoodi luuakse kasutades . Teise veeru ja teise rea elemendid jäetakse nii, nagu nad on. Selles etapis on k teine ​​tipp (st tipp 2). Ülejäänud etapid on samad kui 2. etapis . Arvutage selle tipu 2 kaudu kaugus lähtetippust sihttippuniA2A3
  4. Samamoodi ja on ka loodud. Arvutage selle tipu kaudu kaugus lähtetippust sihttippuni 3 Arvutage selle tipu kaudu kaugus lähtetippust sihttippuni 4A3A4
  5. A4 annab iga tipupaari vahel lühima tee.

Floyd-Warshalli algoritm

n = tippude arv A = maatriks n * n k = 1 kuni n jaoks i = 1 kuni n j = 1 kuni n A k (i, j) = min (A k-1 (i, j) , A k-1 (i, k) + A k-1 (k, j)) tagastab A

Pythoni, Java ja C / C ++ näited

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 Warshalli algoritmi keerukus

Aja keerukus

Silmuseid on kolm. Igal silmusel on pidev keerukus. Niisiis, Floyd-Warshalli algoritmi ajaline keerukus on .O(n3)

Ruumi keerukus

Floyd-Warshalli algoritmi ruumi keerukus on .O(n2)

Floyd Warshalli algoritmirakendused

  • Lühima tee leidmiseks on suunatud graaf
  • Suunatud graafide transitiivse sulgemise leidmiseks
  • Reaalsete maatriksite inversiooni leidmiseks
  • Testimiseks, kas suunamata graaf on kahepoolne

Huvitavad Artiklid...