# Efficiently compute the sum of edge weights product of all possible path in a DAG

I thought of using Depth First Search (DFS) to find all possible paths in O(|V|+|E|). However, computing the product of all the edge weights for a path is O(2^N). Is there any way to compute this more efficiently?

• To clarify: in your problem, each edge $e$ is assigned a weight $w(e)$, and you're meant to compute $\sum_{p} \prod_{e \in p} w(e)$, where the sum is over all paths in a given DAG? – Robert Andrews Oct 22 at 4:12
• Can someone point out some online problem where this needs to be implemented, I would like to write it out and test it. – asds_asds Oct 22 at 4:52
• @RobertAndrews This reply may be late but what you said is correct. – bishopqpalzm Oct 22 at 18:18

You can actually solve this in $$O(|V|+|E|)$$ time. Since it is a DAG, we can apply dynamic programming.

Let $$p = u_1u_2\dots u_k$$ be a path and $$cost(p) = w(u_1,u_2)\times w(u_2,u_3)\times\dots \times w(u_{k-1}, u_k)$$ be the edge weight product of the path. One important observation is that $$cost(u_0p_1) = w(u_0,u_1)\times cost(p_1)$$.

Now, for each node $$u$$, let $$dp(u)$$ be the sum of edge weight products of all paths originating from $$u$$.

Let the children of $$u$$ be $$v_1,v_2,\dots,v_m$$. We can compute $$dp(u)$$ using the relation

$$dp(u)=\sum_{i=0}^m w(u,v_i) \times dp(v_i)$$

A Topological sorting can find the order of nodes to compute. Then, the final answer is the sum of all $$dp$$

$$\sum_{u\in V} dp(u)$$