2
$\begingroup$

Given a directed, acyclic graph in which each node has an assigned integer score, what is a fast way of finding the path from a start and end vertex with the highest cumulative score? I thought of a DFS approach in which we start at the end and run the graph in the reverse way, saving at each node the best cumulative score attainable. To print the results, we start at the first node and greedily pick the next node with the highest cumulative score. However, I don't think this is the best way as we might be traversing the same paths a lot of times if we are given an unfriendly graph. Is there a better way of doing this?

$\endgroup$
4
$\begingroup$

Hint: find a topological ordering, and for each vertex $v$, in the topological ordering, compute (the score of) the path with the highest score that ends at $v$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you! Googling topological ordering was exactly what I needed to do. $\endgroup$ – user1760791 Mar 13 at 4:05

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.