Extracting path information for a directed acyclic graph

Question

For a research problem I am tackling, I have a directed acyclic graph $G(V,E)$. With every node in $V$, I have a variable $y$ associated. Now, given two nodes $i$ and $j$, I would like to have the sum of $y$s of all intervening nodes in all paths between $i$ and $j$.

I am wondering how to extract such information from the incidence or adjacency matrices. I know squaring the adjacency matrix gives me the number of two-edge paths between any two nodes, but more than the number, it is the actual path that I need to sum up $y$s.

I find a lot of CS questions related to this on the Net, where the challenge is to come up with an algorithm to list the paths, but the mathematical formulation is not talked about much.

Answer 1

The number $N(i,j)$ of paths from $i$ to $j$ is given by the matrix $B=E+A+A^2+\dots$. The number of paths from $i$ to $j$ passing through $k$ is $N(i,k)N(k,j)$, which is the number of times you have to take the label of $k$ into acount. Hence the sum over all weights on all paths is $\sum_k N(i,k)N(k,j) y(k)$, where $y(k)$ is the weight attached to the node $k$. This sum is the $(i,j)$-entry of $BDB$, where $D$ is the diagonal matrix with entries $y(k)$. So $BDB$ is the matrix you are looking for.