at 12:11 if bc is of weight -8 then it will make the source weight as negative but it shouldnt be source wt should always be 0 so there this algo will fail?
Bellman ford algorithm
@deepakjumani09
So Bellman Ford algo is especially useful for negative weight edged graphs
In case there is negative weight cycle, after processing is completed it will report that there was a negative weight cycle in which case there will practically exist no shortest path in the graph
You can read more about it here
Kindly close this doubt
ya i know abt the algo but i am asking abt a perticular thing that assume a graph of three vertices edges ab->-8 bc->2 ac->3 undirected graph so this algo will give a weight to a (sourse node) -3 but souce node’s weight should be 0
@deepakjumani09
As I told you, the situation you’re referring to has a negative weight cycle
In which case peculiarities like this will arise and the answer wont make sense
ab=-8 bc=2 and ac=3 has no -ve weighted cycle
@deepakjumani09
Maybe your understanding of negative cycle is not correct.
A negative weight cycle is a cycle with weights that sum to a negative number. The Bellman-Ford algorithm propagates correct distance estimates to all nodes in a graph in V-1 steps, unless there is a negative weight cycle . If there is a negative weight cycle , you can go on relaxing its nodes indefinitely.
In this case sum of weights in cycle is -8 + 2 + 3 which is -3