Tensor's blog

DAG problem .. help ?
By Tensor, 9 years ago, In English

I had been solving this problem

this is my code so far ... any help would be appreciated.

thanks in advance.

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

»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Let Level(X) will be index of vertice X in some topologically sorted vector of vertices. DP(x1, x2, x3) — maximum possible length of 3-path (x1, x2, x3) -> (t1, t2, t3). to calculate DP(x1, x2, x3) you shuld try to move from some of three vertices (x1, x2, x3) with minimum Level.

UPD: vertices are already topologically sorted, Level(x) == x.

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

    It's O(N^4). Maybe there is better solution.

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

      thank you very much

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

      but is what is wrong with my solution ?!

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

        It's wrong. Even bfs is not a BFS.

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

          is that because it can be longest 3-crtical path that the 3 paths are not the longest for each path ??

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

            I did't get your question but I think answer is "Yes".
            your bfs does'nt finds longest path.

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

              that's what i meant... thank you again :-)

              → Reply