Given: G(V,E) DAG, vertex s, and function w: V -> R. (the weight on the vertices)
Define: We define a weighted path in G as sum of all the vertices weight.
Question: Find the heaviest path in G that starts from s. in linear time.
Well, first of all we notice it's DAG, so we can use topological sort here. and also.
My thoughts so far: for each vertex v in G, w(u,v) = w(v). Then my friend told me to multiply by minus one and check for w(p1) < w(p2) before the multiplication iff w(p1) > w(p2). But I'm not sure why it needs to be added.
Then we came up with proceeding with topological sort, relaxing all the edges that are outgoing from the nodes (according to the sort - meaning we start from the heaviest, and we continue with the heaviest edges..)
Time complexity linear.. O(E+V).
My question: If my algorithm is correct, how can I prove it? Is there another algorithm you can think of to solve this question in linear time?