Warshall’s Algorithm

The former method discussed is quite inefficient. Let us see if a more efficient method to compute path can be produced. Let us define the matrix path k such that path k [i][j] is true if and only if there is a path from node i to node j that does not pass through any nodes numbered higher than k (except, possibly, for i and j themselves). How can the value of path k+ J [i][j] be obtained from path k? Clearly for any i and j such that path k [i][j] = true, path k+I [i][j] must be true (why?). The only situation in which path k+1 [i][j] can be true while path k [i][j] equals false is if there is a path from i to j passing through node k + I, but there is no path from i to j passing through nodes i through k. But this means that there must be a path from i to k + 1 passing through nodes i through k and a similar path from k + I to j. Thus path k+ I [i][j] equals true if and only if one of the following two conditions holds:

path k[i][j] == true path k[i][k+1] == true and path k[k+1][j] == true

This means that path k+1[i][j] equals pathk[i][j] || (path k[i][k+1] && path k[k+1][j]). An algorithm to obtain the matrix path k from the matrix path k-1 based on this observation follows

for(i=0; i<MAXNODES; ++i)      for(j=0; j<MAXNODES; ++j)         path[i][j]=path k-1[i][j] || (path k-1[i][k] && path k-1[k][j]);

This may be logically simplified and made more efficient as follows,

for(i=0; i<MAXNODES; ++i)      for(j=0; j<MAXNODES; ++j)         path k[i][j] = path k-1[i][j]; for(i=0;i<MAXNODES; ++i)         if(path k-1[i][k] == TRUE)      for(j=0;j<MAXNODES; ++j)         path k[i][j] = path k-1[i][j] || path k-1[k][j]; Clearly, path 0[i][j] = adj, since the only way to go from node i to node j without passing through any other node is to go directly from i to j. Further, path MAXNODES-1[i][j] = path[i][j], since if a path may pass through any node numbered from 0 to MAXNODES-1, any path from node i to node j may be selected.

This technique increases the efficiency of finding the transitive closure to O(n). The method is often called Warshall's Algorithm, after its discoverer.

Output: