Warshall’s Algorithm

Warshall’s Algorithm

Directed Graph G

Algorithm: (Warshall’s algorithm)

A directed graph G with M nodes is maintained in memory by its adjacency matrix A. This algorithm finds the (Boolean) path matrix P of the graph G.

1. Repeat for I, J = 1, 2, …., M. [Initializes P.]
   If A[I, J] = 0, then:
   Set P[I, J] := 0;Else:Set P[I, J] := 1.[End of loop.]
2. Repeat steps 3 and 4 for K = 1, 2, …., M. [Updates P.]
3. Repeat step 4 for I = 1, 2, ….. M:
4. Repeat for J = 1, 2, …., M:
   Set P[I, J] := P[I, J] v (P[I, K] ^ P[K, J]).[End of loop.]
   [End of step 3 loop.]
   [End of step 2 loop.]
   
5. Exit.