Question

What is the formula to compute the transitive closure of a graph?

(a) tij(k) = tij(k-1) AND (tik(k-1) OR tkj(k-1))

(b) tij(k) = tij(k-1) OR (tik(k-1) AND tkj(k-1))

(c) tij(k) = tij(k-1) AND (tik(k-1) AND tkj(k-1))

(d) tij(k) = tij(k-1) OR (tik(k-1) OR tkj(k-1))

The question was posed to me in unit test.

This intriguing question comes from Shortest Path topic in section Shortest Path of Data Structures & Algorithms II

Answer 1

Correct answer is (b) tij(k) = tij(k-1) OR (tik(k-1) AND tkj(k-1))

Explanation: Transitive closure of a graph can be computed by using Floyd Warshall algorithm. This method involves substitution of logical operations (logical OR and logical AND) for arithmetic operations min and + in Floyd Warshall Algorithm.

Floyd Warshall Algorithm: dij(k)=min(dij(k-1), dik(k-1) + dkj(k-1))

Transitive closure: tij(k)= tij(k-1) OR (tik(k-1) AND tkj(k-1)).