A
sample Warshal algorithm problem. One thing you have to remember
is that, if (1,3) is a valid path then (3,1) is also a valid
path and the warshal algorithm is:
A
direct graph G with M nodes is maintained in memory by its
adjacency matrix A. this algorithm finds the path matrix P of
the graph G.
1.
Repeat for I, J = 1,
2,......,M
If A[I,J]=0, Then Set P[I,J]=0;
Else Set P[I,J] := 1.
2. Repeat
Steps 3 and 4 for k = 1,2, �M:
3.
Repeat Steps 4 for I = 1,2�M:
4.
Repeat for J = 1,2�M:
Set P[I,J] := P[I,J] || (P[I,K]&& P[K,J])
5. Exit.
|