# Still not clear why longest path problem is NP-hard but shortest path is not?

I've heard/read many times that shortest path problem is P, but longest path problem is NP-hard. But I have a problem with this: we say longest path problem is NP-hard because of graphs with positive cycles. But if you think about graphs with one or more negative cycles, we don't have any polynomial time algorithm for the shortest simple path either. In fact, once can be reduced to another.

To summarize, we can find a shortest/longest simple path only if there are no negative/positive cycles. Also we can detect negative/positive cycles with Bellman-Ford in both cases. So under identical criteria, both problems should be considered NP-hard.

• when we say that shortest path is in $P$, it is in non-negative graphs. en.wikipedia.org/wiki/Dijkstra%27s_algorithm "for arbitrary directed graphs with unbounded non-negative weights" – reuns May 5 '16 at 0:53
• That is Dijkstra's limitation. You can find a shortest path in graphs with negative weights (but not negative cycles) with Bellman-Ford, for instance. There's also another algorithm for DAGs with negative weights. – lfk May 5 '16 at 1:31
• yes, I meant graphs without non-negative cycles (since in that case, adding $|\min w|$ to all the weights transforms the graph with negative weights into an equivalent non-negative graph suitable for Dijkstra). so you have no question anymore ? – reuns May 5 '16 at 1:42
• @user1952009: Adding a constant to all edge weights does not lead to an equivalent problem, because it does not add a constant to all path lengths. (Otherwise there would be no need for the Bellman-Ford algorithm.) – Rahul May 5 '16 at 1:50
• @Rahul yes you are right, sorry. do you see anything else to say ? – reuns May 5 '16 at 1:54