LastTry's blog

Directed Acyclic Graph (DAG)
By LastTry, history, 9 years ago, In English

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

  • Vote: I like it
  • -9
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

This is a classic problem in dynamic programming in DAG.

1 — Process the vertices in reverse topological order

2 — 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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    What do you mean by "Process the vertices in reverse topological order"? And how should I do that?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      Do you know what topological sort is? If not I recommend you to read about it, one source is here

      In 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.

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        if I am correct you reversed the topological order for iterating the DP states in correct order

        Yes, 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.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Wow, did you just come online from the big hiatus of codeforces due to this comment or do your frequently lurk?

          → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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.

          → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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/

→ Reply