0

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.

Love Gupta
  • 975
  • 2
  • 16
  • 31
  • Do you need to find shortest path of a node from source? Bellman ford detects if there is any negative edge cycle.. shortest path can't include the negative cycle. – sarthak May 13 '12 at 14:30
  • hey i need to find the shortest path of a node from source in a graph having negative cycle. how to go about doing it? – Love Gupta May 13 '12 at 15:57

2 Answers2

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.

Martin Hock
  • 944
  • 4
  • 5
0

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.

smichr
  • 16,948
  • 2
  • 27
  • 34