Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

Thank you in advance!

share|improve this question
    
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
add comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.