Floyd-Warshall Algorithm in Data Structure
Let G be a directed graph with n vertices 1, 2, 3,…,n. Suppose we want to find the path matrix of G. Warshall gave an algorithm for this purpose. This algorithm is used to calculate the shortest path for a weighted graph.
Path Matrix:
At first, we define n x n Boolean matrices P0, P1,….., Pn as follows:
Pk[i][j]= 1 // If there is a simple path from i to j which does not use any other vertices except possibly 1…k
= 0 // Otherwise
To store the path matrix of graph G, we are taking a two-dimensional array P[][] with order nxn. Initially, the path matrix P is the same as the adjacency matrix. Now Pk[i][j] means we want to traverse from vertex i to vertex j through vertex k. So, Pk[i][j] = 1 if either we can go from vertex i to vertex j through vertex k or vertex j is already reachable from vertex i through some previous vertices. Hence Pk[i][k] = 1 can occur only if one of the following conditions is satisfied:
1. Pk-1[i][j] = 1 (i is reachable from j through some previous vertices)
2. Pk-1[i][k] = 1 and Pk-1[k][j] = 1 (vertex k is reachable from i and j is reachable from k)
Algorithm:
Algorithm fnWarshallPM(n) { First copy the contents of adjacency matrix A to path matrix P; for(i=1;i<=n;i++) for(j=1; j<=n;j++) P[i][j] = A[i][j]; for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) P[i][j] = P[i][j] || (P[i][k] && P[k][j]); } // End of Algorithm