Shortest Path on Data Structure and Algorithms related Questions and Answers

Question :   What is the formula to compute the transitive closure of a graph? 1. tij(k) = tij(k-1) AND (tik(k-1) OR tkj(k-1)) 2. tij(k) = tij(k-1) OR (tik(k-1) AND tkj(k-1)) 3. tij(k) = tij(k-1) AND (tik(k-1) AND tkj(k-1)) 4. tij(k) = tij(k-1) OR (tik(k-1) OR tkj(k-1)) 5. Answer :   2 - tij(k) = tij(k-1) OR (tik(k-1) AND tkj(k-1))