Bellman Ford Shortest path

Question

Is the below statement correct:
Bellman Ford finds all negative weight cycles in the graph.
This is true or false?

Answer 1

Bellman Ford algorithm works, and that it tells if there is a reachable negative cycle. But it does not explicitly name it.Bellman-Ford algorithm reports shortest path only if there is no negative weight cycles. we can Modify it so that it reports minimum distances even if there is a negative weight cycle.

Comments

I am exactly working on this very problem only mam..!!!!!
and just cant figure out how to do this :-
-> The standard Bellman-Ford algorithm reports shortest path only if there is no negative weight cycles. Modify it so that it reports minimum distances even if there is a negative weight cycle.

??? Please help.

Answer 2

If you go through the Bellman Ford algorithm, you are able to get that it detects negative weighted cycle and return FALSE but it does not provide the cycle that has negative weight. We can say that Bellman Ford algorithm informs us that there is a negetive weighted cycle.

Answer 3

As we know bellman Ford don't work on disconnected graph if there is negative edge wt cycle which is unreachable.. So it will respond for only those negative wt cycles which is reachable.. Therefore statement is false as per my opinion..

If we see this with another view it is asking bellman ford can find all negative edge cycles.. Well BF can only report there is negative cycle it won't explicitly name or mention.. So both the way statement is false..

Answer 4

I Just Want To make One Point Here.....Even if there are negative edge Cycle , The Cycle can only be detected if the sum of edge weight of the cycle turns out to be negative ,and other cycles whose sum is +ve will not be detected.....All Negative Edge Cycles Will Not Be Detected.

 

Comments

I want to ask one thing - Bellman ford algo for every weighted graph which contain 2 vertices always produce shortest path.

the statement is True of False?

---

False.