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

0
votes

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.

1
data-structuresbellman-fordsingle-source
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
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

1 Answers

1
votes

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.