# Counting paths of a variable length on a directed graph

If I've been given a directed Graph $G = (V,E)$ and its adjacency matrix $A$. How do I calculate how many (directed) paths do exist from one specific node to another (specific) one?

In general $a_{v,w}^{(n)}$ which is the n-th power of the entry $a_{v,w}$ of $A$ is the answer I am looking for (for the amount of pathes of the length $n$ from node $v$ to node $w$). But how do I determine an explicit formula for a variable n?

-
 I assume you are only interested in directed paths, right? Otherwise, the adjacency matrix A of an undirected graph is symmetric and so it can be diagonalized as A=$S^{-1}DS$, where D is the eigenvalue matrix of A, and S has the eigenvectors associated to the eigenvalues in D. This gives you a nice way of calculating $A^n$; specifically, the S's and the $S^{-1}$'s in the products will cancel out: $A^n=[S^{-1}DS]^n$=$S^{-1}DS(S^{-1}DS)....$ and you will end up with:$A^n$=$S^{-1}D^nS$ – gary Jul 2 '11 at 21:17 @gary Yes, I am only interested in directed paths. – muffel Jul 3 '11 at 8:39

One way to do this is using Jordan normal form. It works well if you can write down the eigenvectors of $A$ explicitly. But there is another way. Consider the matrix generating function

$$(I - At)^{-1} = \sum_{n \ge 0} A^n t^n.$$

The coefficient of $t^n$ is precisely a matrix whose values describe the number of paths of length $n$ between the vertices of $G$. On the other hand, this is just the inverse of a matrix $I - At$, so its entries can be computed using the adjugate, which gives

$$(I - At)^{-1} = \frac{\text{adj}(I - At)}{\det(I - At)}$$

hence

$$\sum_{n \ge 0} (A^n)_{ij} t^n = \frac{ \text{adj}(I - At)_{ij} }{\det(I - At)}.$$

But $\text{adj}(I - At)_{ij}$ is easy to calculate. Thus the generating function for the sequence you want can be explicitly written as the ratio of two polynomials which are easy to compute given $A$, and then you can use partial fraction decomposition to turn this into an explicit formula.

If you are less interested in an explicit formula than just efficiently computing $(A^n)_{ij}$, then it may be more productive to just compute $A^n$ using binary exponentiation.

-
 I guess you can also use Gaussian elimination to compute the inverse of $I - At$ instead, but for small graphs the above should be fine; in any case you only have to do the computation once per graph. – Qiaochu Yuan Jul 2 '11 at 22:06 thank you for this solution! – muffel Jul 3 '11 at 21:20

Let $E_p$ be the set of edges in some initial path. Then for each edge $e_{\alpha} \in E_p$, define a new graph $G_{e_{\alpha}} = (V,E \setminus \{e_{\alpha}\})$ being the initial graph with that edge removed. If there are no paths from $v$ to $w$ in this graph, let $S_{e_{\alpha}} = \{\}$ the empty set. Otherwise, define $S_{e_{\alpha}}$ recursively as the set of paths (where each path is defined like $E_p$ as the set of edges in the path) from $v$ to $w$ in the graph $G_{e_{\alpha}}$, or equivalently, the set of paths from $v$ to $w$ in the graph $G$ that do not use the edge $e_{\alpha}$.

Then the total number of paths should be one more than the cardinality of the union of all $S_{e_{\alpha}}$. If you want to count only paths of a given length $n$, you can simply define a new set $S_n \subseteq \bigcap S_{e_{\alpha}}$ as the set of all paths of length $n$. Then simply use the cardinality of this set.

Unfortunately this approach will not be terribly efficient, since you have to keep re-calculating the paths. I'll be interested to see if someone has an approach that's more efficient.

-