FLOYD'S ALGORITHM
Introduction
Floyd's Algorithm is also known as "All Pair Shortest Path Problem". This algorithm finds the lengths of the shortest paths from each vertex to all other vertices for a given weighted graph.
So far in our discussion related to graph, we store the graph in an adjacency graph whose values are 0s or 1s. In weighted graph, we store the weights(in place of 1s) of the respective edges. If there is no edges between a certain pair of vertices then the weight shall be treated to be infinity.
Working Procedure
The input shall be an adjacency weighted matrix and 100 shall be entered instead of infinity(or any other higher integer than all the weights).
-
Loop from k=0 to n-1.
-
Loop from i=0 to n-1.
-
Loop from j=0 to n-1.
- D[i][j] = min(D[i][j] , D[i][k]+D[k][j]).
-
Loop from j=0 to n-1.
-
Loop from i=0 to n-1.
Initially we consider the vertex k as a mid-point and check if the length of path from vertex i to j through k(i->k + k->j) is lesser than the existing length of direct path(i->j). If yes, then the new length shall be stored as the shortest length from i to j, else the old length shall remain as it is.
Time Complexity: O(n3)
Code file
Please open this in your pc or with a compatible app in your mobile.
C++ Implementation for FLOYD'S ALGORITHMThat's it from this blog post. If you liked it then do share this blog with your friends or people who wanna get into programming world. Thank You!