V tomto výučbe sa dozviete, ako funguje algoritmus floyd-warshall. Nájdete tiež pracovné príklady algoritmu floyd-warshall v jazykoch C, C ++, Java a Python.
Floyd-Warshall Algorithm je algoritmus na nájdenie najkratšej cesty medzi všetkými pármi vrcholov vo váženom grafe. Tento algoritmus funguje pre smerované aj neorientované vážené grafy. Nepracuje to však s grafmi so zápornými cyklami (kde je súčet hrán v cykle záporný).
Vážený graf je graf, v ktorom má každý okraj priradenú číselnú hodnotu.
Algoritmus Floyd-Warhshall sa tiež nazýva Floydov algoritmus, Roy-Floydov algoritmus, Roy-Warshallov algoritmus alebo WFI algoritmus.
Tento algoritmus sleduje prístup dynamického programovania s cieľom nájsť najkratšie cesty.
Ako funguje Floyd-Warshallov algoritmus?
Nech je daný graf:
Počiatočný graf
Podľa nasledujúcich pokynov nájdete najkratšiu cestu medzi všetkými dvojicami vrcholov.
- Vytvorte maticu dimenzie, kde n je počet vrcholov. Riadok a stĺpec sú indexované ako i, respektíve j. i a j sú vrcholy grafu. Každá bunka A (i) (j) je vyplnená vzdialenosťou od vrcholu k vrcholu. Ak neexistuje cesta z vrcholu do vrcholu, bunka sa ponechá ako nekonečno. Vyplňte každú bunku vzdialenosťou medzi i-tym a j-tym vrcholom
A0n*nithjthithjth
- Teraz vytvorte maticu pomocou matice . Prvky v prvom stĺpci a prvom riadku sú ponechané tak, ako sú. Zvyšné bunky sa vyplnia nasledujúcim spôsobom. Nech k je stredný vrchol na najkratšej ceste od zdroja k cieľu. V tomto kroku je k prvý vrchol. je naplnený . To znamená, že ak je priama vzdialenosť od zdroja k cieľu väčšia ako cesta cez vrchol k, potom je bunka naplnená . V tomto kroku je k vrchol 1. Cez tento vrchol k vypočítame vzdialenosť od zdrojového k cieľovému. Vypočítajte vzdialenosť od zdrojového k cieľovému vrcholu cez tento vrchol k Napríklad: Pre
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), priama vzdialenosť od vrcholu 2 k 4 je 4 a súčet vzdialenosti od vrcholu 2 k 4 cez vrchol (tj. od vrcholu 2 k 1 a od vrcholu 1 k 4) je 7. Pretože4 < 7, je vyplnený 4.A0(2, 4) - Podobne sa vytvára pomocou . Prvky v druhom stĺpci a druhom rade sú ponechané tak, ako sú. V tomto kroku je k druhý vrchol (tj vrchol 2). Zvyšné kroky sú rovnaké ako v kroku 2 . Vypočítajte vzdialenosť od zdrojového vrcholu k cieľovému vrcholu cez tento vrchol 2
A2A3
- Podobne a je tiež vytvorený. Vypočítajte vzdialenosť od zdrojového vrcholu k cieľovému vrcholu cez tento vrchol 3 Vypočítajte vzdialenosť od zdrojového vrcholu k cieľovému vrcholu cez tento vrchol 4
A3A4
A4dáva najkratšiu cestu medzi každou dvojicou vrcholov.
Floyd-Warshallov algoritmus
n = počet vrcholov A = matica rozmeru n * n pre k = 1 až n pre i = 1 až n pre j = 1 až n A k (i, j) = min (A k-1 (i, j) , A k-1 (i, k) + A k-1 (k, j)) návrat A
Príklady jazyka Python, Java a 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); )
Zložitosť algoritmu Floyda Warshalla
Časová zložitosť
Existujú tri slučky. Každá slučka má neustále zložitosti. Takže časová zložitosť algoritmu Floyd-Warshall je .O(n3)
Zložitosť vesmíru
Priestorová zložitosť algoritmu Floyd-Warshall je .O(n2)
Floyd Warshall Algorithm Applications
- Najkratšiu cestu nájdete pomocou smerovaného grafu
- Ak chcete nájsť prechodné uzavretie smerovaných grafov
- Nájsť inverziu skutočných matíc
- Na testovanie toho, či je neusmernený graf bipartitný
