Number of paths starting from a given edge using adjacency matrix

Question

I want to write the algorithm that takes the adgacency matrix of a directed connected graph without any cycles, then for each edge computes the number of paths starting from that edge. Also note that there is at most one edge between two nodes.

For example consider the graph depicted below: For instance, we want to count the number of paths starting from edge $b$. They are: $b, bd, bdf, bdfg, bh$. So $F(q0, q2)=5$. ($F$ is the function that runs the counting algorithm). As another example $F(q4, q5)=2$.

Note that I want to count these paths for every two distinct nodes. So the output must be a matrix.

How should I write the algorithm? And what will be the complexity of that?

Answer 1

Note that counting the number of (non empty) paths starting from edge $(q_1, q_2)$ is the same as counting the number of (possibly empty) paths starting from vertex $q_2$. That way, the answer can be given as an array of size $|V|$ for a graph $G = (V, E)$ instead of a matrix of size $|V| \times |V|$.

Knowing that fact, here is an algorithm to compute this array $a$:

• compute a topological sort $(v_1, …, v_n)$ of $G$ (this is possible because $G$ is supposed to be acyclic);
• for $k$ from $n-1$ to $1$, set $a[v_k] = 1+\sum\limits_{v \text{ adjacent to }v_k} a[v]$, since $(v_k, v)\in E$, that means that $v$ appears after $v_k$ in the topological sort, so the value $a[v]$ has already been computed. Moreover, if the sum is empty, it means that $v_k$ is a sink node, meaning it has no exiting edge, so the only path is the empty path.

The algorithm has a total complexity $O(|V| + |E|)$, which is optimal.

Now, note that the complexity of the previous algorithm suppose you know the adjacency list of the graph $G$. If you only know the adjacency matrix of $G$, then I suggest you first compute the adjacency list of $G$ (time complexity $O(|V|^2)$).