Similar to Floyd-Warshall’s Algorithm, this algorithm uses a matrix to calculate the transitive closure of all pairs of nodes in a directed graph.
It also breaks on negative cycles!
Pseudocode
Algorithm Transitive_Closure(G):
T ← |V| x |V| array
//Initialise the T matrix
For i from 1 to |V| do:
For j from 1 to |V| do:
If i=j or edge i-j exists in G then:
T[i][j] ← 1
Else:
T[i][j] ← 0
End if
End do
End do
For k from 1 to |V| do:
From i from 1 to |V| do:
From j from 1 to |V| do:
If T[i][j] = 1 OR (T[i][k] = 1 AND T[k][j] = 1) then:
T[i][j] ← 1
End if
End do
End do
End do
Return T
End Algorithm