Does a polynomial time shortest path algorithm exist given that both source and target verteces are reachable from a negative cycle?

Question

I'm not asking for an algorithm to check the existence of a negative cycle in a graph(Bellman Ford or Floyd Warshall can do that), rather whether or not there exists a polynomial time algorithm to find the shortest path between two points when the graph contains at least one negative cycle that is reachable from the source vertex and the target vertex can be reached from the negative cycle.

Answer 1

If you are looking for a path (no repeating vertices) then this problem is NP hard. You can reduce longest path problem to this one by simply multiplying weights by -1.

The main difference between classical (only positive weights on edges) shortest path (which is in P) and longest path problem (which is NP-complete) is following: All polynomial shortest path algorithms are basically calculating shortest walk, but since you have positive weight on edges, the shortest walk is also shortest path (repeating edges does not decrease the length of walk). In longest path problem you have to somehow check for uniqueness of vertices on the path.

When you have negative cycle, then the Bellman-Ford algorithm calculates the length of the shortest walk which has at most N edges.