Proof that shortest path with negative cycles is NP hard
Copied from my answer on cstheory.stackexchange.com:



Paths with no repeated vertices are called simple-paths, so you are looking for the shortest simple-path in a graph with negative-cycles.

This can be reduced from the longest-path problem.  If there were a fast solver for your problem, then given a graph with only positive edge-weights, negating all the edge-weights and running your solver would give the longest path in the original graph.

Thus your problem is NP-Hard.