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.

  • 1
    $\begingroup$ 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" $\endgroup$ – reuns May 5 '16 at 0:53
  • $\begingroup$ 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. $\endgroup$ – lfk May 5 '16 at 1:31
  • $\begingroup$ 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 ? $\endgroup$ – reuns May 5 '16 at 1:42
  • $\begingroup$ @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.) $\endgroup$ – Rahul May 5 '16 at 1:50
  • $\begingroup$ @Rahul yes you are right, sorry. do you see anything else to say ? $\endgroup$ – reuns May 5 '16 at 1:54

The longest path problem is commonly understood as follows: given a graph, find the longest simple path. Simple means that no vertex is visited more than once. Only in graphs with cycles can a vertex be visited more than once. The shortest path problem, however, is commonly defined for simple paths in acyclic graphs.

The difficulty for finding simple paths in graphs (possibly containing cycles) is easy to prove from the Hamiltonian path, i.e., a path visiting all the vertices. The reduction is easy, just assign length 1 to all edges. A Hamiltonian path exists iff the longest path has length n-1.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.