Warshall's 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, ......., : [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, J] ^ P[K, J]).

[End of loop].

[End of Step 3 loop]

5.Exit.

If You want to learn about the technology, computer science & engineering, web programming, freelancing, earning please click here :CSE SOLVE