Sum of path products in DAG
Posted
by
Jules
on Stack Overflow
See other posts from Stack Overflow
or by Jules
Published on 2012-04-12T11:26:09Z
Indexed on
2012/04/12
11:28 UTC
Read the original article
Hit count: 350
Suppose we have a DAG with edges labeled with numbers. Define the value of a path as the product of the labels. For each (source,sink)-pair I want to find the sum of the values of all the paths from source to sink. You can do this in polynomial time with dynamic programming, but there are still some choices that can be made in how you decompose the problem. In my case I have one DAG that has to be evaluated repeatedly with different labelings. My question is: for a given DAG, how can we pre-compute a good strategy for computing these values for different labelings repeatedly. It would be nice if there was an algorithm that finds an optimal way, for example a way that minimizes the number of multiplications. But perhaps this is too much to ask, I would be very happy with an algorithm that just gives a good decomposition.
© Stack Overflow or respective owner