Week 3: Graph Data Structures and Algorithms (114)

Transitive Closure (cont)

If we implement the above as:

make tc[][] a copy of edges[][]
for all i∈vertices(G) do
   for all s∈vertices(G) do
      for all t∈vertices(G) do
         if tc[s][i]=1 and tc[i][t]=1 then
            tc[s][t]=1
         end if
      end for
   end for
end for

then we get an algorithm to convert edges into a tc

This is known as Warshall's algorithm