1
$\begingroup$

I was given a directed acyclic graph $G=(V,E)$ that has red and blue edges, and I want to generate a path from vertex $s$ to vertex $t$ such that the path has a maximum number of red edges.

After thinking about this I've decided to let every blue edge have a cost $0$ and every red edge to have a cost of $1$, which I think is the same problem.

I'm trying to use dynamic programming to generate this path but I'm confused on how to approach this to run this in linear time.

$\endgroup$
1
$\begingroup$

If the vertices are already in topological order (that is, all edges go from left to right) then you can start at $s$ and go in order. For each vertex, compute the maximum cost path from $s$ to that vertex, by considering all the edges that point into that vertex.

This takes $O(|V|+|E|)$ time.

If the vertices are not already sorted this way, then you should look at one of these algorithms for fixing that. These also take $O(|V|+|E|)$ time.

In general, this is nearly always the setup for dynamic programming in a directed acyclic graph, just because the topological sort is the primary way we can take advantage of the lack of cycles.

$\endgroup$
  • $\begingroup$ Yes now I need to to write the formula to fill my path array(result) $\endgroup$ – user3133165 Jan 26 at 16:49

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.