How to get Single Source Shortest Path for graphs having a negative weight cycle

Question

Hey i have been studying the bellman ford algorithm for "single source shortest path" problems.

Now i am stuck at one point where i need to find out the solution for a graph having negative weight cycle.

But Bellman ford algorithm does not work here.

Can some one suggest me what to do. How to solve a problem having negative weight cycle?

Thanks for your time.

Answer 1

If there is a negative cycle which is reachable from the origin, which Bellman-Ford can detect, then you have two choices: either allow repeating edges, or do not. If you allow repeating edges, your shortest path could be considered to be infinitely negative. Otherwise, if you do not, the problem is NP complete. From Wikipedia:

One NP-Complete variant of the shortest-path problem asks for the shortest path in G (containing a negative cycle) such that no edge is repeated.

Answer 2

In a paper here discussed here the authors (Wulff-Nilson, Nanongki, Berstein) mention that a graph with negative-weight cycles can be reduced to one without such cycles and then they give a method that finds the shortest path in nearly linear time.