Take the 2-minute tour ×

What might be a good way to calculate length of all paths between two nodes in a directed acyclic graph? I don't need the actual paths, just the length. Is there a combinatorial formula for that?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

Let $A$ be the adjacency matrix for your graph - so $A_{ij}=1$ if $(i,j)$ is an edge of your graph and $(A_{ij}=0$ otherwise.

Then $(A^k)_{ij}$ is the number of paths from $i$ to $j$ of length $k$.

One nice property is that, since the graph is acyclic, there can be no path of length $\geq n$, where $n$ is the number of nodes in your graph, since such a path would have to have a cycle. This means that $A^n=0$.

You can easily get the number of paths from $i$ to $j$ by taking the $ij$th entry of $I+A+A^2+...+A^{n-1}=(I-A)^{-1}$, so you need only invert $I-A$ to get all the counts.

I'm not seeing how to get the counts of the lengths, or even the list of lengths, other than explicitly computing $A^k$ for each $k$.

share|improve this answer
Thanks. I ll need to do a bit of search. –  rivu Jun 26 '12 at 19:14

Your Answer


