# Proof that shortest path with negative cycles is NP hard

I'm looking into the shortest path problem and am wondering how to prove that shortest path with neg. cycles is NP-hard. (Or is it NPC? Is there a way to validate in P time that the path really is shortest?)

How would I reduce the SAT problem into the shortest path problem in polynomial time?

• Do you have to reduce from SAT? A simple reduction is from Hamiltonian path.
– Juho
Jun 2, 2019 at 11:02
• The decision version of your problem is: Given a graph and a number $\ell$, is there a path whose length is shorter than $\ell$? This is clearly in NP. Jun 2, 2019 at 18:33