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?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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$.
-
$\begingroup$ Thank you! Googling topological ordering was exactly what I needed to do. $\endgroup$ Commented Mar 13, 2020 at 4:05