struggling with this question from an exam:
input:
DAG G=(V,E). each edge $e_i$ has weight $w_i\in \text{{0,1,2,3}} $
Two vertices : s,t
Number: k
output:
A path from s to t with total cost k (if exists)
$\begingroup$
$\endgroup$
-
$\begingroup$ What have you tried? Where did you get stuck? $\endgroup$ – dkaeae Jul 15 '19 at 13:16
-
$\begingroup$ tried to transform the problem into exact length of k and didn't really know how to continue. $\endgroup$ – qksr55789 Jul 16 '19 at 7:53
$\begingroup$
$\endgroup$
When you get a question about a DAG, the first thing to do is a topological sort.
Now, go through all vertexes in order. For each vertex $v$, keep all the possible costs of a path from $s$ to $v$; there will be no more than $3V$ distinct costs. For each edge $e(v,u)$, add to $u$ the costs of $v$ + the weight of $e$.
-
$\begingroup$ thank you for the reply. why would there be no more than 3V distincs costs? do you mean in each vertex 3V possible costs or the total costs of all vertices ? $\endgroup$ – qksr55789 Jul 16 '19 at 7:50
-
$\begingroup$ For each vertex v, the maximal possible paths weight from s to v. The maximal weight of an edge is 3, the maximal length of a path is V (there are no circles) so the maximal number of possible paths weight is 3*V. $\endgroup$ – Shuki Avraham Jul 16 '19 at 8:33
-
