2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Robert Andrews Oct 22 at 4:12
  • $\begingroup$ Can someone point out some online problem where this needs to be implemented, I would like to write it out and test it. $\endgroup$ – asds_asds Oct 22 at 4:52
  • $\begingroup$ @RobertAndrews This reply may be late but what you said is correct. $\endgroup$ – bishopqpalzm Oct 22 at 18:18
3
$\begingroup$

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)$$

$\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.