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?
7
-
$\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 GodsilJun 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$– user24732Jun 27, 2012 at 0:17
-
$\begingroup$ This is an easy dynamic programming exercise. Is it homework? $\endgroup$– Brendan McKayJun 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$– Hugh DenoncourtJun 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$– Brendan McKayJun 27, 2012 at 4:31
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
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.
