Given DAG $G(V,E)$, find $\forall v \in V$ the sum of the weights of vertices that are reachable from the $v$

Question

Given a DAG $G=(V,E)$ and a weights function on the vertices $w:V \to \mathbb{R}$, suggest an algorithm that computes for every $v \in V$ the sum of the weights of vertices that are reachable from it.

My idea is to use topological sort on the graph and then start from the end to the start, and for each vertex $v \in V$ set the sum to $S(v)=w(v)+\sum_{(v, u) \in E} S(u)$.

But this can cause counting some vertices multiple times, which I am not sure how to fix while still solving the problem in linear time.

Answer 1

In order to avoid the double counting you can work with sets of vertices instead of their sums of weights. Let's denote $R(v)$ a set of all vertices, reachable from the vertex $v$. Then, similarly to your formula, you can calculate all the $R(v)$ sets scanning vertices in backward topological order:

$$R(v)=v \cup \bigcup_{(v, u) \in E} R(u)$$

After this process is finished you can calculate the sum of weights for each vertex $v \in V$ using its $R(v)$ set. However this algorithm won't be linear - even the last step will take $O(|V|^2)$ time, because you'll need to process the set $R(v)$ for each $v \in V$.

These $R(v)$ sets actually represent the Transitive Closure of the graph $G$ - finding the transitive closure of a DAG is a well known problem, and the best known algorithm for it takes $O(|V|^{2.373})$ time. Also please see this question (and its answers), which is very similar to what you've asked.

Answer 2

You can do better, so we propose a linear time algorithm.

Reverse the edges of $G$ in linear time, name it $G^R$, and start from the last node in topological order of $G$ in $G^R$, so propagate sum of values from the last node to other nodes that reachable from it in $G^R$. This can be done in $\mathcal{O}(n+m).$