CODEWITHSUNDEEP
algorithmgraphshortest-pathdijkstralongest-path
Sumukh Bhat
Sumukh Bhat

Reputation: 91

Question about single source longest path in a DAG

If I am right, the problem of single source longest path for any general graph is NP-hard.

Can we negate all the edge weights of a DAG and run Dijstra's or Bellman Ford algorithm to get single source longest path?

If yes, Dijstra's can't run on a graph with negative edge weights, then how come it gives us a result will all negative edge weights?

Upvotes: 1

Views: 214

Answers (1)

Berthur
Berthur

Reputation: 4495

Yes, you are right. Your proposed solution can be used to find a longest path in a DAG.

However, notice that the longest path problem for a DAG is not NP-hard. It is NP-hard for the general case where the graph might not be a DAG. There is some interesting, relevant discussion on Wikipedia's article on the Longest path problem.

As for your second question, Dijkstra's algorithm is defined for non-negative edge weights. The implementation might give you a result anyway, but it is no longer guaranteed to be correct.

Upvotes: 1

Related Questions