Directed acyclic graph problem

Question

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!

Answer 1

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$

Answer 2

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.