Collapsing a directed acyclic graph to its sink

Question

I have the following algorithm: Given a single sink, directed acyclic graph $D = (V, E)$,

1. Associate each node $v \in V$ with a number $r(v) = n_v$

2. Then, for each neighbor $v \in N^{+}(s)$ of each source node $s$, do $r(v) = r(v) + \displaystyle\sum_\limits{v \in N^{+}(s)}\frac{r(s)}{|N^{+}(s)|}$

3. Remove each current source node, Repeat step 2 for the new source nodes. Terminate when the sink node is reached.

I am trying to prove that for the sink node $z$, $r(z) = \displaystyle\sum_{v \in V}n_{v}$

But I don't know where to start the proof. Any hint or advice?

Answer 1

I assume that for each vertex $v\in V$ we have $N^+(v)=\{u\in V: (v,u)\in E\}$.

It is natural to start from the beginning of the construction and follow it. We see that the sum $\sum r(v)$ at each step is constant. But at the first step it equals $\sum_{v\in V} n_v$, whereas at the last it equals $r(z)$.