0
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.