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?

## 1 Answer

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.

2more comments