Reachability matrix in time $O(|V| \cdot |E|)$

Question

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

Answer 1

This algorithm doesn't work. Consider a graph with four vertices 1,2,3,4 and edges $1\to2\to3\to4$. Your algorithm outputs $T(1,4)=0$ even though 4 is reachable from 1.

The running time analysis of the algorithm can be improved to $O(VE)$. The first loop takes time $O(V^2)$. The number of pairs $(v,u)$ in the second loop is the number of edges $E$, and for each pair $(v,u)$, the maximal number of $w$s is $V$. So the second loop runs in time $O(VE)$.

Answer 2

This answer summarizes some of the comments. The well-known Floyd–Warshall algorithm runs in time $O(V^3)$, and there is a matrix multiplication based algorithm running in time $O(V^\omega)$, which is however not so useful in practice.

The following algorithm runs in time $O(V(V+E))$. Starting at each vertex $v$, run a DFS/BFS from $v$ to find all nodes reachable from $v$. This is not quite $O(VE)$, but given that the output size $V^2$, the $V^2$ term in the running time is unavoidable.

What if we don't want to output the entire matrix, but only the non-zero entries? In this case we can modify this algorithm to run in time $O(VE)$. First we use DFS/BFS to find all the connected components. Let $V_i,E_i$ be the number of vertices and edges in the $i$th component, and note that $E_i \geq V_i-1$. We run the previous algorithm on each connected component, thus achieving a running time of $O(\sum_i V_i(V_i+E_i)) = O(\sum_i V_iE_i)$. Using $V_i \leq V$ and $\sum_i E_i = E$, we see that the overall running time is $O(VE)$ (in addition to $O(V+E)$ for the initial BFS/DFS).

In fact, this modification isn't really needed. The running time of BFS/DFS in component $i$ is $O(V_i+E_i) = O(E_i)$, and so the running time of the original algorithm is in fact only $O(\sum_i V_i E_i) = O(VE)$, given that we don't output the entire matrix but only the non-zero entries.