Psyf/DataStructsAndAlgos-2040C

cs2010_AY1314S1_final

Opened this issue · 1 comments

0WN463 commented
  1. Finding the longest path in a weighted graph when all edges are non-positive is an easy
    problem that has solution with polynomial time complexity
  2. NP-Hard. So no.

Hmm, if you multiply all the weights by -1, doesn't it becomes a question of shortest path given positive weights? Assuming longest path here means least negative

Psyf commented

You get to the problem of negative weight cycles. This is as of yet undefined in 2040C.