567

Risk
Type:
Graph
Diff: 3.0

Tricks

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.

 

Related Problems & Topics

 

If you have any advice, complements 

or proposal, please  Send mail to Author

Submit

 

1