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?

  • $\begingroup$ 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? $\endgroup$ Jun 26, 2012 at 21:27
  • $\begingroup$ 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. $\endgroup$
    – user24732
    Jun 27, 2012 at 0:17
  • $\begingroup$ This is an easy dynamic programming exercise. Is it homework? $\endgroup$ Jun 27, 2012 at 1:14
  • $\begingroup$ That did not occur to me, though it does now. What kind of course would it be an exercise in? $\endgroup$ Jun 27, 2012 at 1:21
  • $\begingroup$ @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. $\endgroup$ Jun 27, 2012 at 4:31

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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