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?
length of paths between two nodes in a directed acyclic graph
1
$\begingroup$
combinatorics
graph-theory
1 Answers
2
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$.
-
0Thanks. I ll need to do a bit of search. – 2012-06-26