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?
$\begingroup$
$\endgroup$
3
-
$\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 AndrewsCommented Oct 22, 2019 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_asdsCommented Oct 22, 2019 at 4:52
-
$\begingroup$ @RobertAndrews This reply may be late but what you said is correct. $\endgroup$– bishopqpalzmCommented Oct 22, 2019 at 18:18
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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)$$