Floyd-Warshall algoritmas

Šioje pamokoje sužinosite, kaip veikia „Floyd-Warshall“ algoritmas. Taip pat rasite veikiančių „floyd-warshall“ algoritmų pavyzdžių C, C ++, „Java“ ir „Python“.

„Floyd-Warshall“ algoritmas yra algoritmas, leidžiantis rasti trumpiausią kelią tarp visų viršūnių porų svertiniame grafike. Šis algoritmas veikia tiek nukreiptiems, tiek nekreiptiems svertiniams grafikams. Bet tai neveikia grafikams su neigiamais ciklais (kai ciklo briaunų suma yra neigiama).

Svertinis grafikas yra grafikas, kuriame kiekvienas kraštas turi skaitinę vertę.

Floyd-Warhshall algoritmas taip pat vadinamas Floyd'o, Roy-Floydo, Roy-Warshall'o arba WFI algoritmu.

Šis algoritmas vadovaujasi dinaminio programavimo metodu, kad surastų trumpiausius kelius.

Kaip veikia Floyd-Warshall algoritmas?

Leiskite pateiktam grafikui būti:

Pradinis grafikas

Norėdami rasti trumpiausią kelią tarp visų viršūnių porų, atlikite toliau nurodytus veiksmus.

  1. Sukurkite matmenų matricą , kur n yra viršūnių skaičius. Eilutė ir stulpelis indeksuojami atitinkamai i ir j. i ir j yra grafiko viršūnės. Kiekviena ląstelė A (i) (j) užpildoma atstumu nuo viršūnės iki viršūnės. Jei nuo viršūnės iki viršūnės nėra kelio , ląstelė paliekama kaip begalybė. Užpildykite kiekvieną langelį atstumu tarp i-osios ir j-osios viršūnėsA0n*n
    ithjthithjth
  2. Dabar sukurkite matricą naudodami matricą . Pirmojo stulpelio ir pirmos eilutės elementai paliekami tokie, kokie yra. Likę langeliai užpildomi tokiu būdu. Tegul k yra tarpinė viršūnė trumpiausiu keliu nuo šaltinio iki paskirties. Šiame etape k yra pirmoji viršūnė. yra užpildytas . Tai yra, jei tiesioginis atstumas nuo šaltinio iki paskirties yra didesnis nei kelias per viršūnę k, tada ląstelė užpildoma . Šiame etape k yra viršūnė 1. Apskaičiuojame atstumą nuo šaltinio viršūnės iki paskirties viršūnės per šią viršūnę k. Apskaičiuokite atstumą nuo šaltinio viršūnės iki paskirties viršūnės per šią viršūnę k Pavyzdžiui: Už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), Tiesioginis Atstumas nuo viršūnių 2 iki 4 yra 4 ir atstumo suma iš nario 2 iki 4 per viršūnių (ty. Iš viršūnių 2 iki 1 ir nuo viršūnių 1 iki 4) yra 7. Nuo 4 < 7, yra pripildyta 4.A0(2, 4)
  3. Panašiai yra sukurta naudojant . Antrojo stulpelio ir antrosios eilutės elementai paliekami tokie, kokie yra. Šiame etape k yra antroji viršūnė (ty 2 viršūnė). Likę veiksmai yra tokie patys kaip 2 žingsnyje . Apskaičiuokite atstumą nuo šaltinio viršūnės iki paskirties viršūnės per šią 2 viršūnęA2A3
  4. Panašiai ir yra sukurta. Apskaičiuokite atstumą nuo šaltinio viršūnės iki paskirties viršūnės per šią viršūnę 3 Apskaičiuokite atstumą nuo šaltinio viršūnės iki paskirties viršūnės per šią viršūnę 4A3A4
  5. A4 pateikia trumpiausią kelią tarp kiekvienos viršūnių poros.

Floyd-Warshall algoritmas

n = nėra viršūnių A = matrica dimensijos n * n, k = 1 iki n i = nuo 1 iki n, j = nuo 1 iki n A k (i, j) = min (A K-1 (i, j) , A k-1 (i, k) + A k-1 (k, j)) grąžina A

„Python“, „Java“ ir „C / C ++“ pavyzdžiai

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

Floydo Warshallo algoritmų kompleksiškumas

Laiko kompleksiškumas

Yra trys kilpos. Kiekviena kilpa turi nuolatinį sudėtingumą. Taigi Floyd-Warshall algoritmo sudėtingumas yra laikas .O(n3)

Erdvės sudėtingumas

Floyd-Warshall algoritmo erdvės sudėtingumas yra .O(n2)

Floydo Warshallo algoritmo programos

  • Norėdami rasti trumpiausią kelią, reikia nukreipti grafiką
  • Norėdami rasti nukreiptą grafikų tranzityvų uždarymą
  • Norėdami rasti tikrųjų matricų inversiją
  • Norėdami patikrinti, ar nenukreiptas grafikas yra dvipusis

Įdomios straipsniai...