829 views
2 votes
2 votes
If there is a negative edge cycle present in a graph, we all know that Bellman Ford has the capability to detect it. My doubt is that, even after the presence of a negative weighted cycle, will Bellman Ford Algorithm give the correct answer or it will simply say NO..shortest path cannot be computed!?

1 Answer

Best answer
1 votes
1 votes

 After the presence of a negative weighted cycle,  Bellman Ford Algorithm cannot give the correct answer reason is:

If a graph contains a "negative cycle" (i.e. a cycle whose edges sum to a negative value) that is reachable from the source, then there is no cheapest path: any path that has a point on the negative cycle can be made cheaper by one more walk around the negative cycle. In such a case, the Bellman–Ford algorithm can detect negative cycles and report their existence.

It will simply detect negative edge weight cycles and report their existence only.

selected by

Related questions

0 votes
0 votes
2 answers
2
2 votes
2 votes
4 answers
4
Bongbirdie asked Apr 6, 2017
1,810 views
Is the below statement correct:Bellman Ford finds all negative weight cycles in the graph.This is true or false?