### LastTry's blog

By LastTry, history, 6 years ago,

Hey, guys!

I've been working on a problem recently but I need some help with the idea of it. Here it is:

You are given a directed acyclic graph with the length of the edges between two vertices. What you have to do is find the longest path in the graph, starting from the beginning vertex (it's 1). The input contains on the first line the number of vertices (N) and number of edges (M). Then it is followed by M lines, each of whom contains 3 numbers — the first 2 are the indexes of the two vertices which are connected and the 3rd number is the length of the edge between them. The output should contain the longest path in the DAG.

Example input:

5 8 1 2 5 1 4 4 1 5 1 2 3 3 2 5 1 4 3 2 5 3 3 5 4 2

Example output:

10

Explanation: Here's the path in this case: 1 2 5 4 3

• -9

 » 6 years ago, # |   +6 This is a classic problem in dynamic programming in DAG.1 — Process the vertices in reverse topological order2 — If a vertex v has outgoing edges, D[v] = max(D[v], w(v, u) + D[u]), otherwise D[v] = 0, where w(u,v) is the cost of the edge v to u.
•  » » 6 years ago, # ^ |   +5 What do you mean by "Process the vertices in reverse topological order"? And how should I do that?
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +1 Do you know what topological sort is? If not I recommend you to read about it, one source is hereIn short (and without being formal) it means you arrange all the vertices in a line such that all edges go from left to right (this is always possible in a DAG). In this problem you don't need to do this arrangement explicitly — I'll leave the details as an exercise for you = ), though if you struggle feel free to ask again.
•  » » » » 6 years ago, # ^ |   0 Thanks, if I need help I hope it's not a problem to ask. :)
•  » » 22 months ago, # ^ |   0 what if we do not process the nodes in reverse order? i think that will not change anything.
•  » » 7 weeks ago, # ^ |   0 Hello, ivanilos, can you please explain the intuition behind the reverse topological ordering.Why we need to reverse? Will not the answer be same without reversing the ordering.Asking on a blog written 6 years ago, as I searched for topological sorting and hit this blog. So it will be helpful if you can explain the intuition.
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 Again sorry to disturb you, ivanilos, if I am correct you reversed the topological order for iterating the DP states in correct order as without reversing it we will hit the DP state we have not processed till yet.Can you please confirm ? Will be very helpful if you can clear the doubt.
•  » » » » 7 weeks ago, # ^ |   +3 if I am correct you reversed the topological order for iterating the DP states in correct orderYes, you are correct. This way of iteration of states is also known as "bottom up".Will not the answer be same without reversing the ordering.It is also possible to solve it in a way called "top down" but I felt it was easier to understand and explain the bottom up approach.
•  » » » » » 7 weeks ago, # ^ |   +3 Wow, did you just come online from the big hiatus of codeforces due to this comment or do your frequently lurk?
•  » » » » » 7 weeks ago, # ^ |   +3 Thank you very much ivanilos, you replied to a blog written 6 years ago. I was not hoping but really thanks for taking out your time and clearing the doubt.
 » 6 years ago, # |   0 Is there any other source where I can read more about DP on DAG?
 » 6 years ago, # |   0 I think you can take the negative of all edge weights and apply the Bellman–Ford Algorithm. Your final answer will be the negative of the answer given by Bellman–Ford Algorithm. This works because, Bellman–Ford Algorithm is used to calculate the shortest path from source node to every other node. Now, if you negate all edge weights, then the abs(length of shortest path) = length of longest path. You can read more about Bellman–Ford Algorithm here — http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/