title: Why finding the longest path in a graph is NP-hard
body: <p>This <a href="https://en.wikipedia.org/wiki/Longest_path_problem" rel="noreferrer">link</a> mentions:</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>So why is finding the longest path an NP-hard problem if this transformation can reduce it to the shortest path problem?</p>
  
  <p>After the transformation, we have have these cases:</p>
  
  <ul>
  <li><code>-G</code> has a negative cycle, in which case the shortest path in <code>-G</code> cannot be found</li>
  <li><code>-G</code> does not have a negative cycle, in which case Floy-Warshall or Bellman-Ford algorithm can find the shortest path in <code>-G</code> in polynomial time</li>
  </ul>
  
  <p><strong>Questions:</strong> </p>
  
  <ol>
  <li><p>Is it correct to say if there is no negative cycle, the problem of finding longest path is not NP-hard?</p></li>
  <li><p>Is it correct to say in the presence of negative cycles, there is still a longest <code>simple path</code> between nodes which is NP-hard to be found?</p></li>
  <li><p>If so, is it more accurate to say finding the longest <strong>simple</strong> path in a graph is NP-hard?</p></li>
  <li><p>If so, because of <code>-G</code> transformation is it also correct to say that finding the shortest <strong>simple</strong> path in a graph is also NP-hard?</p></li>
  </ol>
  
  <p><strong>Edit</strong></p>
  
  <p>This link explains the confusion about longest path problem in more details:
  <a href="https://hackernoon.com/shortest-and-longest-path-algorithms-job-interview-cheatsheet-2adc8e18869" rel="noreferrer">https://hackernoon.com/shortest-and-longest-path-algorithms-job-interview-cheatsheet-2adc8e18869</a></p>