This link mentions:
A longest path between two given vertices s and t in a weighted graph G is the same thing as a shortest path in a graph −G derived from G by changing every weight to its negation. Therefore, if shortest paths can be found in −G, then longest paths can also be found in G.
So why is finding the longest path an NP-hard problem if this transformation can reduce it to the shortest path problem?
After the transformation, we have have these cases:
-G has a negative cycle, in which case the shortest path in -G cannot be found-G does not have a negative cycle, in which case Floy-Warshall or Bellman-Ford algorithm can find the shortest path in -G in polynomial timeQuestions:
Is it correct to say if there is no negative cycle, the problem of finding longest path is not NP-hard?
Is it correct to say in the presence of negative cycles, there is still a longest simple path between nodes which is NP-hard to be found?
If so, is it more accurate to say finding the longest simple path in a graph is NP-hard?
If so, because of -G transformation is it also correct to say that finding the shortest simple path in a graph is also NP-hard?
Edit
This link explains the confusion about longest path problem in more details: https://medium.com/hackernoon/shortest-and-longest-path-algorithms-job-interview-cheatsheet-2adc8e18869
The confusion here is that the Longest Path Problem generally asks for the longest simple path, i.e., the longest path without repeated vertices. For this reason, it can be reduced to the Hamiltonian Path problem, which is known to be NP-hard.
Bellman-Ford and similar algorithms, on the other hand, compute the shortest path in a graph (note: without simple), i.e. vertices can be repeated.
So your four questions:
-G, a longest path does not exist at all in G, because you can just continue walking around the cycle forever. A longest simple path might still exist, but with or without negative cycle, the problem can be reduced to Hamiltonian Path and is therefore still NP-hard.