2
$\begingroup$

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!

  • 0
    @gary Yes, I am only interested in directed paths.2011-07-03

2 Answers 2

3

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.

  • 0
    thank you for this solution!2011-07-03
1

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.