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$ – Chris Godsil Jun 26 '12 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 '12 at 0:17
  • $\begingroup$ This is an easy dynamic programming exercise. Is it homework? $\endgroup$ – Brendan McKay Jun 27 '12 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$ – Hugh Denoncourt Jun 27 '12 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$ – 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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