Suppose that we are given a directed graph and we want to find out if a vertex $j$ is reachable from another vertex $i$ for all vertex pairs $(i, j)$ in the given graph. Reachable mean that there is a path from vertex $i$ to $j$. The reachability matrix is called transitive closure of a graph.
I want to write an algorithm that rus in time $O(|V| \cdot |E|)$ and calculates the transitive closure of a directed graph $G=(V,E)$.
I have tried the following:
Transitive_Closure(G)
for v=1 to |V|
for u=1 to |V|
T(v,u)=0
for v=1 to |V|
for each u in Adj[v]
T(v,u)=1
for each w in Adj[u]
T(v,w)=1
But isn't the time complexity $O(|V| \cdot |E|^2)$? Or am I wrong?
This algorithm definitely finds the transition matrix, but it's even in $\Omega(|V|^3)$:
Transitive_Closure(G)
for i = 1 to |V|
for j = 1 to |V|
T[i,j]=A[i,j] // A is the adjacency matrix of G
for k = 1 to |V|
for i = 1 to |V|
for j = 1 to |V|
T[i,j]=T[i,j] OR (T[i,k] AND T[k,j])
EDIT: Is the following algorithm right?
Transitive_Closure(G)
1. for each vertex u in G.V
2. for each vertex v in G.V
3. T[u,v]=0
4. for each vertex u in G.V
5. BFS(G,u)
6. return T
BFS(G,s)
1. for each vertex u in G.V-{s}
2. color[u]=WHITE
3. d[u]=inf
4. pi[u]=NIL
5. color[s]=GRAY
6. d[s]=0
7. pi[s]=NIL
8. Q=empty set
7. ENQUEUE(Q,s)
8. while Q!= empty set
9. u=DEQUEUE(Q)
10. for each v in G.Adj[u]
11. if color[v]==WHITE
12. color[v]=GRAY
13. d[v]=d[u]+1
14. pi[v]=u
17. ENQUEUE(Q,v)
18. color[u]=BLACK
19. T[s,u]=1