Floida-Varshola algoritms

Šajā apmācībā jūs uzzināsiet, kā darbojas Floyd-Warshall algoritms. Jūs atradīsit arī piemērus Floyd-Warshall algoritmam C, C ++, Java un Python.

Floida-Varšala algoritms ir algoritms, lai svērtā grafikā atrastu īsāko ceļu starp visiem virsotņu pāriem. Šis algoritms darbojas gan virzītajiem, gan nenovirzītajiem svērtajiem grafikiem. Bet tas nedarbojas grafikiem ar negatīviem cikliem (kur cikla malu summa ir negatīva).

Svērtais grafiks ir grafiks, kurā katrai malai ir saistīta skaitliskā vērtība.

Floyd-Warhshall algoritmu sauc arī par Floida algoritmu, Roy-Floyd algoritmu, Roy-Warshall algoritmu vai WFI algoritmu.

Šis algoritms izmanto dinamiskās programmēšanas pieeju, lai atrastu īsākos ceļus.

Kā darbojas Floida-Varshola algoritms?

Ļaujiet dotajam grafikam būt:

Sākotnējais grafiks

Veiciet tālāk norādītās darbības, lai atrastu īsāko ceļu starp visiem virsotņu pāriem.

  1. Izveidojiet dimensijas matricu , kur n ir virsotņu skaits. Rinda un kolonna ir indeksētas attiecīgi kā i un j. i un j ir diagrammas virsotnes. Katra šūna A (i) (j) ir piepildīta ar attālumu no virsotnes līdz virsotnei. Ja no virsotnes uz virsotni nav ceļa , šūna tiek atstāta kā bezgalība. Aizpildiet katru šūnu ar attālumu starp i un j virsotniA0n*n
    ithjthithjth
  2. Tagad izveidojiet matricu, izmantojot matricu . Pirmās kolonnas un pirmās rindas elementi tiek atstāti tādi, kādi tie ir. Atlikušās šūnas tiek aizpildītas šādā veidā. Ļaujiet k būt starpposma virsotne īsākajā ceļā no avota līdz galamērķim. Šajā solī k ir pirmā virsotne. ir piepildīts ar . Tas ir, ja tiešais attālums no avota līdz galamērķim ir lielāks nekā ceļš caur virsotni k, tad šūna ir piepildīta . Šajā solī k ir virsotne 1. Mēs aprēķinām attālumu no avota virsotnes līdz mērķa virsotnei caur šo virsotni k. Aprēķiniet attālumu no avota virsotnes līdz mērķa virsotnei caur šo virsotni k Piemēram: ParA1A0
    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), tiešais attālums no 2. līdz 4. virsotnei ir 4, un attāluma no 2. līdz 4. virsotnei caur virsotni (ti, no 2. līdz 1. un no 1. līdz 4. virsotnei) summa ir 7. Tā kā 4 < 7, ir piepildīta ar 4.A0(2, 4)
  3. Līdzīgi tiek izveidots, izmantojot . Elementi otrajā kolonnā un otrajā rindā tiek atstāti tādi, kādi tie ir. Šajā solī k ir otrā virsotne (ti, virsotne 2). Pārējās darbības ir tādas pašas kā 2. darbībā . Aprēķiniet attālumu no avota virsotnes līdz galamērķa virsotnei caur šo 2. virsotniA2A3
  4. Līdzīgi, un arī tiek izveidots. Aprēķiniet attālumu no avota virsotnes līdz galamērķa virsotnei caur šo virsotni 3 Aprēķiniet attālumu no avota virsotnes līdz galamērķa virsotnei caur šo virsotni 4A3A4
  5. A4 dod īsāko ceļu starp katru virsotņu pāri.

Floida-Varshola algoritms

n = neviens no virsotnes A = matrica no dimensijas n * n, k = 1 līdz n i = 1 līdz n j = 1 līdz n A k (i, j) = min (A k-1 (i, j) , A k-1 (i, k) + A k-1 (k, j)) atgriež A

Python, Java un C / C ++ piemēri

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

Floida Varshola algoritmu sarežģītība

Laika sarežģītība

Ir trīs cilpas. Katrai cilpai ir nemainīga sarežģītība. Tātad Floida-Varshola algoritma laika sarežģītība ir .O(n3)

Kosmosa sarežģītība

Floida-Varshola algoritma telpas sarežģītība ir .O(n2)

Floida Varshola algoritmu lietojumi

  • Lai atrastu īsāko ceļu, ir vērsts grafiks
  • Lai atrastu virzītu grafu transitīvo slēgšanu
  • Lai atrastu reālo matricu inversiju
  • Lai pārbaudītu, vai nenovirzīts grafiks ir divpusējs

Interesanti raksti...