# length of paths between two nodes in a directed acyclic graph

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?

• It's not clear what you are asking for. Do you want to determine the set of possible lengths of paths from one vertex to another? – Chris Godsil Jun 26 '12 at 21:27
• suppose a and b are two vertices in a DAG (V,E). There are m paths between A and B. What is the best way to determine length of each of m paths from a to b? I need to do this for all pairs (a,b) that belongs to V. – user24732 Jun 27 '12 at 0:17
• This is an easy dynamic programming exercise. Is it homework? – Brendan McKay Jun 27 '12 at 1:14
• That did not occur to me, though it does now. What kind of course would it be an exercise in? – Hugh Denoncourt Jun 27 '12 at 1:21
• @Hugh: an algorithms course. The standard algorithm for shortest paths in acyclic digraphs (which is a generalization of most textbook examples of dynamic programming, such as longest common substring) is easily adapted. For $n$ vertices and $m$ edges, it is easy to do it in time $O(mn)$. A lower bound is $n^2$ since that is how large the answer can be, but at the moment I don't see how to do it that fast. – Brendan McKay Jun 27 '12 at 4:31

Label the vertices from 1 to $n$. Let $A = (a_{ij})$ be the incidence matrix. (The entry $a_{ij}$ is 1 if there is an arrow from vertiex $i$ to vertex $j$ and $a_{ij} = 0$ otherwise.)
Then, the number of paths from vertex $i$ to vertex $j$ of length $k$ is the $a_{ij}$ entry of $A^k$. (This is a well known result that follows from the definitions of matrix multiplication and incidence matrix.)
So, you can determine the (multi-)set of path lengths from $i$ to $j$ by forming each of the $n$ powers and looking at the $a_{ij}$ entry.