Флоид-Варсхалл алгоритам

У овом упутству ћете научити како функционише алгоритам флоид-варсхалл. Такође, наћи ћете радне примере флоид-варсхалл алгоритма на Ц, Ц ++, Јава и Питхон.

Флоид-Варсхалл алгоритам је алгоритам за проналажење најкраће путање између свих парова темена у пондерисаном графу. Овај алгоритам ради и за усмерене и за усмерене пондерисане графиконе. Али, то не функционише за графиконе са негативним циклусима (где је збир ивица у циклусу негативан).

Пондерисани граф је граф у коме је уз сваку ивицу повезана нумеричка вредност.

Флоид-Вархсхалл алгоритам се назива и Флоидов алгоритам, Рои-Флоид алгоритам, Рои-Варсхалл алгоритам или ВФИ алгоритам.

Овај алгоритам прати приступ динамичког програмирања да би се пронашли најкраћи путеви.

Како функционише Флоид-Варсхалл Алгоритхм?

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

Почетни графикон

Следите кораке у наставку да бисте пронашли најкраћи пут између свих парова темена.

  1. Направите матрицу димензија где је н број врхова. Ред и колона индексирају се као и, односно ј. и и ј су темена графикона. Свака ћелија А (и) (ј) попуњена је растојањем од темена до темена. Ако нема путање од темена до темена, ћелија остаје као бесконачност. Попуните сваку ћелију растојањем између и-ог и ј-тог теменаA0n*n
    ithjthithjth
  2. Сада креирајте матрицу користећи матрицу . Елементи у првој колони и првом реду остали су такви какви јесу. Преостале ћелије се попуњавају на следећи начин. Нека је к средњи врх на најкраћем путу од извора до одредишта. У овом кораку, к је први врх. је испуњен са . Односно, ако је директна удаљеност од извора до одредишта већа од путање кроз врх к, тада је ћелија испуњена . У овом кораку, к је врх 1. Израчунавамо удаљеност од изворног до одредишног темена кроз овај врх к. Израчунајте удаљеност од изворног темена до одредишног темена кроз овај к к На пример: За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, испуњена 4.A0(2, 4)
  3. Слично томе, креира се помоћу . Елементи у другој колони и другом реду остали су такви какви јесу. У овом кораку, к је други врх (тј. Врх 2). Преостали кораци су исти као у кораку 2 . Израчунајте удаљеност од изворног до одредишног темена кроз овај врх 2A2A3
  4. Слично томе, и такође је створено. Израчунај удаљеност од изворног врха до одредишног темена кроз овај врх 3 Израчунај удаљеност од изворног врха до одредишног темена кроз овај врх 4A3A4
  5. A4 даје најкраћи пут између сваког пара темена.

Флоид-Варсхалл алгоритам

н = број темена А = матрица димензија н * н за к = 1 до н за и = 1 до н за ј = 1 до н А к (и, ј) = мин (А к-1 (и, ј) , А к-1 (и, к) + А к-1 (к, ј)) враћа А

Примери за Питхон, Јава и Ц / Ц ++

Питхон Јава Ц Ц ++ 
 # 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)

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

Сложеност простора Флоид-Варсхалл алгоритма је .O(n2)

Примене алгоритма Флоид Варсхалл

  • Да бисте пронашли најкраћи пут, усмерени граф је
  • Да би се пронашло прелазно затварање усмерених графова
  • Да би се пронашла Инверзија реалних матрица
  • За испитивање да ли је неусмерени графикон дводелни

Занимљиви Чланци...