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?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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. 

