Erich Prisner
UMUC SG
Spring 2002
Warshall's Algorithm
See the adjacency matrix of one of the graphs shown by clicking on
the corresponding graph button.
Click 11 times on the "increase m" button to see the transitive closure.
Am denotes reachability where only paths
with only intermediate vertices 1,2,...m
are allowed.
We use the formula
am(i,j) = am-1(i,j) + am-1(i,m)*am-1(m,j)