Problem
We can solve shortest path problem on graphs with negative weights, with one caveat: If the graph contains a negative cycle, we can not force the algorithm to find the shortest simple path from s to t (a simple path is a path that does not visit a vertex twice).
In this problem, you need to prove that HP≤P Shortest-Simple-Path, where Shortest- Simple-Path is the shortest simple path problem, and HP is the Hamiltonian path prob- lem. (Though we did not prove this in class, it is known that HP is NP-complete. So this suggests Shortest-Simple-Path is also NP-complete.)
You can assume the Shortest-Simple-Path problem is a decision problem: we are given a graph G = (V, E) with (possibly negative) edge weights w: E → R, two different vertices s, t ∈ V and a threshold L ∈ R. We need to decide if the shortest simple path from s to t in G has weight at most L or not.
Also, recall that in the HP problem, we are given a graph G = (V, E) and two different vertices s and t, and we need to output if there is a Hamiltonian path between s and t in G or not.