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.

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.
