Given DAG G(V,E), and weight on the vertices, find the heaviest path that starts from s

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?

• Your solution is just the iterative version of the standard dynamic programming solution to this kind of problem. The recursive version is probably more natural. – md5 Jul 28 '17 at 13:40
• Cross-posted: stackoverflow.com/q/45268906/781723. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. – D.W. Jul 28 '17 at 16:24
• @D.W. I will be posting from now on here. Thanks for pointing out. – Ilan Aizelman WS Jul 28 '17 at 16:33

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.

• The link you added is exactly the algorithm in the post. I think I got it now. it works only for DAG, otherwise it'd be NP-Hard. Thanks Fade! – Ilan Aizelman WS Jul 28 '17 at 13:04

Actually you can solve it using Djkastra's algorithm in linear time if weights are not negative.

This algo finds the minimum distance from one to all nodes, so if you want to find the maximum distance you need to consider negative of the weight of edges.

That is why your friend was telling to check for -ve(weight).

• Do you understand what "check for w(p1) < w(p2) before the multiplication iff w(p1) > w(p2)" means? – D.W. Jul 28 '17 at 16:15
• @D.W. Can you explain please? – Ilan Aizelman WS Jul 28 '17 at 16:33
• See in this algo two edges(weight) are compared and minimum is taken into account first.Let say weights are 5 and 15 so vertex related to '5'(weight) will be visited first, but if you want maximum weight graph then vertex corresponding to '15' should be visited first. If you need to implement this without changing whole algo just take negative of weight and then compare i.e b/w '-5' and '-15' which one is less, '-15' so vertex corresponding to this edge will be visited. – Prateek Mirdha Jul 28 '17 at 17:21