Алгоритъм на Флойд-Уоршал

В този урок ще научите как работи алгоритъмът на floyd-warshall. Също така ще намерите работещи примери за алгоритъм на floyd-warshall в C, C ++, Java и Python.

Алгоритъмът на Floyd-Warshall е алгоритъм за намиране на най-краткия път между всички двойки върхове в претеглена графика. Този алгоритъм работи както за насочени, така и за неориентирани претеглени графики. Но това не работи за графиките с отрицателни цикли (където сумата от ръбовете в един цикъл е отрицателна).

Претеглена графика е графика, в която всеки ръб има свързана с него числова стойност.

Алгоритъмът на Floyd-Warhshall се нарича още алгоритъм на Floyd, алгоритъм на Roy-Floyd, алгоритъм на Roy-Warshall или WFI.

Този алгоритъм следва подхода на динамичното програмиране, за да намери най-кратките пътища.

Как работи алгоритъмът на Floyd-Warshall?

Нека дадената графика бъде:

Начална графика

Следвайте стъпките по-долу, за да намерите най-краткия път между всички двойки върхове.

  1. Създайте матрица с размерност, където n е броят на върховете. Редът и колоната се индексират съответно като i и j. i и j са върховете на графиката. Всяка клетка A (i) (j) се запълва с разстоянието от върха до върха. Ако няма път от връх до връх, клетката се оставя като безкрайност. Напълнете всяка клетка с разстоянието между i-ти и j-ти връхA0n*n
    ithjthithjth
  2. Сега създайте матрица, използвайки матрица . Елементите в първата колона и първия ред са оставени такива, каквито са. Останалите клетки се попълват по следния начин. Нека k е междинният връх в най-краткия път от източника до местоназначението. В тази стъпка k е първият връх. е изпълнен с . Тоест, ако директното разстояние от източника до местоназначението е по-голямо от пътя през върха k, тогава клетката се запълва с . В тази стъпка k е връх 1. Изчисляваме разстоянието от върха на източника до върха на дестинацията през този връх k. Изчислете разстоянието от изходния връх до върха на дестинацията през този връх k Например: За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), Прякото разстояние от връх 2 до 4 е 4, а сумата от разстоянието от връх 2 до 4 чрез връх (т.е.. От връх 2 до 1 и от връх 1 до 4) е 7. Тъй като 4 < 7, е изпълнен с четири.A0(2, 4)
  3. По същия начин се създава с помощта на . Елементите във втората колона и втория ред са оставени такива, каквито са. В тази стъпка k е вторият връх (т.е. връх 2). Останалите стъпки са същите като в стъпка 2 . Изчислете разстоянието от изходния връх до върха на дестинацията през този връх 2A2A3
  4. По същия начин, и също е създаден. Изчислете разстоянието от върха на източника до върха на дестинацията през този връх 3 Изчислете разстоянието от върха на изхода до върха на дестинацията през този връх 4A3A4
  5. A4 дава най-краткия път между всяка двойка върхове.

Алгоритъм на Флойд-Уоршал

n = брой на върховете A = матрица с размерност n * n за k = 1 до n за i = 1 до n за j = 1 до n A k (i, j) = min (A k-1 (i, j) , A k-1 (i, k) + A k-1 (k, j)) връща A

Примери за Python, Java и 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); )

Сложност на алгоритъма на Флойд Уоршал

Сложност във времето

Има три цикъла. Всеки цикъл има постоянни сложности. И така, сложността във времето на алгоритъма на Флойд-Уоршал е .O(n3)

Сложност на пространството

Космическата сложност на алгоритъма на Floyd-Warshall е .O(n2)

Приложения на алгоритъма на Floyd Warshall

  • За да намерите най-краткия път е насочена графика
  • За да се намери преходното затваряне на насочени графики
  • Да намерим инверсията на реални матрици
  • За тестване дали неориентираната графика е двустранна

Интересни статии...