Floyd Warshall Algorithm
Finding the shortest path has always been a tricky thing, the most optimal path which would result in the lowest time of travel.
The algorithm, Floyd–Warshall, is utilized to track down the briefest ways between all sets of vertices in a chart, where each edge in the diagram has a weight that is either — negative or positive.
The algorithm is also called WFI algorithm or Roy-Warshall algorithm.
This algorithm follows the principles of Dynamic Programming to estimate the shortest paths.
Algorithm
First of all,
Let’s assume a graph of x vertices,
where x is the number of vertices.
First step being, that between the any two vertices of graph, initializing the shortest paths with infinity.
Second step being, finding all the pairs of shortest paths that have 0 intermediate vertices, then proceeding to finding the ones having 1 intermediate vertices and so on and so forth, until having used up all the X vertices as intermediate nodes.
Third step being, from the previous operation, minimizing the shortest paths between any two pairs.
Fourth step being, for any 2 vertices (X,Y), one ought to really limit the distances between this pair utilizing the primary Z hubs, so the briefest way will be: min(D[X][Z]+D[Z][Y],D[X][Y]).
D[X][Z] represents the shortest path that only uses the first K vertices, D[Z][Y] represents the shortest path between the pair Z,Y.
As the most limited way will be a link of the briefest way from X to Z, at that point from Z to Y.
The code for performing the following operation:
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] );
}
}
}EXPLANATION:
Here the given graph would be, as drawn in the image, following the procedures:
Now, following the certain steps listed below to find all the shortest path between all the pairs of vertices in the given figure and the general algorithm.
Proceeding through the steps one by one, listing it with the help of figures.
STEPS:
> Here, now first thing would be creating a Matrix A⁰ with the dimension n², where n denotes the vertices. i and j are respectively used as row and column portrayal, being i and j are also the vertices of the given graph.
So, the process basically is, every cell A[i][j] is loaded up with the separation from the ith vertex to the jth vertex. In the event that there is no way from ith vertex to jth vertex, the cell is left as infinity.
> Here, we are using the Matrix A⁰ to create another Matrix A¹, the way elements in the first column and first row are, have been left as they are. And now to fill up the remaining ones, we use the following method:
> Now, assuming that here, k would be the freezing vertex (in the shortest path) from the given source to the destination. Following this, in the step, k would be the first vertex so the way A[i][j] would be filled with is, (A[i][k] + A[k][j]) if (A[i][j] > A[i][k] + A[k][j]).
> And here if, the distance that is direct from the source to the destination > the path from the vertex k, it would be (cell) filled in A[i][k] + A[k][j] way.
> Now in this step, vertex 1 is k and we are calculating the distance from it to the destination vertex from vertex k.
Here is the Matrix A¹, created through the following steps given above.
Now, for explaining, here taking an example of A¹[2,4], we have the direct distance 4 from the vertex 2 to 4 and sum is 7. So, here, 4 < 7, A⁰[2,4] is been filled with 4.
Now, the same way, we created the Matrix A¹ using the Matrix A⁰, applying the rules, the Matrix A³ would also be created in a similar fashion.
Moving on, same way, Matrix A⁴ would also be created, which would give the shortest path between the given pairs of vertices.
COMPLEXITY (TIME AND SPACE):
As we’ve seen above in code, there are 3 loops used, every loop with a constant complexity, so the resulting complexity would be O(n³). This would be time complexity of Floyd-Warshall Algorithm.
And the space complexity for the Floyd-Warshall Algorithm is O(n²).
