U ovom vodiču naučit ćete kako funkcionira algoritam floyd-warshall. Također ćete naći radne primjere floyd-warshall algoritma na C, C ++, Java i Python.
Floyd-Warshall algoritam algoritam je za pronalaženje najkraćeg puta između svih parova vrhova u ponderiranom grafu. Ovaj algoritam radi i za usmjereni i za neusmjereni ponderirani graf. Ali, to ne funkcionira za grafikone s negativnim ciklusima (gdje je zbroj bridova u ciklusu negativan).
Ponderirani graf je graf u kojem svaki rub ima pridruženu numeričku vrijednost.
Floyd-Warhshall algoritam naziva se i Floydovim algoritmom, Roy-Floydovim algoritmom, Roy-Warshallovim algoritmom ili WFI algoritmom.
Ovaj algoritam slijedi pristup dinamičkom programiranju kako bi pronašao najkraće putove.
Kako djeluje Floyd-Warshall algoritam?
Neka zadani graf bude:
Početni graf
Slijedite korake u nastavku kako biste pronašli najkraći put između svih parova vrhova.
- Stvorite matricu dimenzija gdje je n broj vrhova. Redak i stupac indeksiraju se kao i, odnosno j. i i j su vrhovi grafa. Svaka ćelija A (i) (j) ispunjena je udaljenostom od vrha do vrha. Ako ne postoji put od vrha do vrha, ćelija ostaje kao beskonačnost. Ispunite svaku ćeliju razmakom između i-og i j-tog vrha
A0n*nithjthithjth
- Sada stvorite matricu pomoću matrice . Elementi u prvom stupcu i prvom redu ostaju takvi kakvi jesu. Preostale ćelije popunjavaju se na sljedeći način. Neka je k srednji vrh na najkraćem putu od izvora do odredišta. U ovom je koraku k prvi vrh. je ispunjen s . Odnosno, ako je izravna udaljenost od izvora do odredišta veća od putanje kroz vrh k, tada je ćelija ispunjena . U ovom koraku k je vrh 1. Izračunavamo udaljenost od izvornog vrha do odredišnog vrha kroz ovaj vrh k. Izračunajte udaljenost od izvornog vrha do odredišnog vrha kroz ovaj vrh k Na primjer: Za
A1A0A(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 izravna udaljenost od vrha 2 do 4, 4, a zbroj udaljenosti od vrha 2 do 4, preko vrha (tj. Od vrha 2 do 1 i od vrha 1 do 4) je 7. Od4 < 7, napunjen s 4.A0(2, 4) - Slično tome, stvara se pomoću . Elementi u drugom stupcu i drugom redu ostaju takvi kakvi jesu. U ovom je koraku k drugi vrh (tj. Vrh 2). Preostali koraci su isti kao u koraku 2 . Izračunajte udaljenost od izvornog vrha do odredišnog vrha kroz ovaj vrh 2
A2A3
- Slično tome, i također je stvoreno. Izračunajte udaljenost od izvornog vrha do odredišnog vrha kroz ovaj vrh 3 Izračunajte udaljenost od izvornog vrha do odredišnog vrha kroz ovaj vrh 4
A3A4
A4daje najkraći put između svakog para vrhova.
Floyd-Warshall algoritam
n = broj vrhova A = matrica 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)) povratak A
Primjeri Pythona, Java i 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); )
Složenost algoritma Floyda Warshalla
Složenost vremena
Postoje tri petlje. Svaka petlja ima stalne složenosti. Dakle, vremenska složenost Floyd-Warshallovog algoritma je .O(n3)
Složenost prostora
Prostorna složenost Floyd-Warshallovog algoritma je .O(n2)
Primjene algoritma Floyda Warshalla
- Da bi se pronašao najkraći put usmjereni je graf
- Da bi se pronašlo prijelazno zatvaranje usmjerenih grafova
- Da bi se pronašla inverzija stvarnih matrica
- Za ispitivanje je li neusmjereni graf dvostrani
