0
$\begingroup$

Love some guidance on this problem:

G is a directed acyclic graph. You want to move from vertex c to vertex z. Some edges reduce your profit and some increase your profit. How do you get from c to z while maximizing your profit. What is the time complexity?

Thanks!

$\endgroup$
0
$\begingroup$

Algorithm:

  • Remove nodes unreachable from $c$.
  • Sort $G$ topologically.
  • Consider vertices in topological order and assign them profit $$\mathrm{profit}(v) = \max_{(u,v)\ \in\ E}\Big(\mathrm{profit}(u) + \mathrm{cost}\big((u,v)\big)\Big)$$

Try to prove why this greedy strategy works and what is its running time.

I hope that helps $\ddot\smile$

$\endgroup$
0
$\begingroup$

A minor modification of Dijkstra's algorithm will solve the problem, where instead of looking for the path with the lowest weight we are looking for the path with the highest weight.

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