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?
Given DAG G(V,E), and weight on the vertices, find the heaviest path that starts from s
algorithms
Try to transform the graph as following. Assign weight 0 to each edge and then split each vertex into two vertices by connecting them by an edge with the weight equal to the vertex's weight.   ====>(12)====>   turns into  =====>(v)--12-->(u)====>The find the longest path in $O(|V| + |E|)$. Please look here.