WARSHALL'S ALGORITHM
Introduction
Warshall’s algorithm is used for computing the transitive closure of a directed graph. From the relations concept, w.k.t that if a relates to b and b relates to c and a relates to c then there is a transitive relation.
Recall from the adjacency matrix of a digraph, the entry in ith row and jth column is 1 if and only if there exists an edge from vertex i to j. So here, we are interested to find a matrix that holds the information about the existence of directed paths of arbitrary lengths between vertices of a given graph.
Such a matrix, called the transitive closure of the digraph, would allow us to determine in constant time whether the jth vertex is reachable from the ith vertex.
Working Procedure
-
Loop from k=0 to n-1.
-
Loop from i=0 to n-1.
-
If R[i][k]==1 then loop from j=0 to n-1.
- If R[k][j]==1 then R[i][j]=1.
-
If R[i][k]==1 then loop from j=0 to n-1.
-
Loop from i=0 to n-1.
It simply means that, if R[i,k]==1 and R[k,j]==1 then assign R[i,j]=1 and this says that we can reach vertex j starting from vertex i.
Time Complexity: O(n3)
Code file
Please open this in your pc or with a compatible app in your mobile.
C++ Implementation for WARSHALL'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!