peoplePleaser's blog

Longest Path in a weighted DAG
By peoplePleaser, history, 3 years ago, In English

Does there exist a way an efficient method to find the longest path in a DAG among all possible paths? I know how to solve this in $$$O(V*(V+E))$$$ by considering each vertex as the source, and then using topo sort, and iterating over the vertices in that order and update the distances accordingly. Any suggestions/help would be appreciated or maybe we can prove there doesn't exist a faster method. Thanks!

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by peoplePleaser (previous revision, new revision, compare).

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

Auto comment: topic has been updated by peoplePleaser (previous revision, new revision, compare).

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

The algorithm you described should be $$$O(V+E)$$$, because you can just relax each edge once in your topo-sort order.

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

    It's $$$O(V+E)$$$ if we fix the source vertex, right? but we need to find the longest path over all possible paths.

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

      Just initialize all vertices to have value 0 instead of -INF; alternatively, make a super-source that connects to all vertices.

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

        Thanks, I thought of this solution. But how to handle the case when all weights are negative? We will always end up with a value of zero, right?

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

          You can store longest non-empty path, in which case you relax $$$val[v] = \max(val[v], \max(val[u], 0) + e)$$$

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

            Thanks got it!

            My bad! I am such a fool, if all weights are negative, the answer is the largest (least negative) weight edge.

            → Reply