java - What exactly happens in the Bellman-Ford Algorithm if there is a negative weigth cycle? -

i'm trying understand why bellman-ford algorithm not work negative weight cycle. understand negative weight cycles prevent program giving right answer. happens in program if there negative weight cycle?

thanks help

the bellman-ford algorithm finds shortest path source vertex other vertices in weighted graph.

the issue negative-weight cycles there no shortest-path.

without drawing, consider case of 4 nodes, source, , nodes b,c,d other vertices.

weights of edges follows:

w(a,b) = 1 w(b,c) = 1 w(c,d) = 1 

bellman-ford conclude following shortest path lengths

path(a~b) = 1 path(a~c) = 2 path(a~d) = 3 

but if added edge created negative weight cycle. example edge c b weight of -2.

w(c,b) = -2 

now there negative weight cycle. walking (b,c,b) total path weight of -1 (1 + -2).

if run bellman-ford again, give thinks shortest-path d did previously.[note 1]

but time, wrong.

in fact, wouldn't matter integer shortest path weight algorithm gave because always find 1 shorter.

for example, algorithm gave original path weight of 3 (a,b,c,d). well, it's easy see construct shorter path: (a,b,c,b,c,d) gives path weight of 2.

but that's not shortest path either. example (a,b,c,b,c,b,c,d) gives path weight of 1.

as can see, can construct arbitrarily short path weight repeatedly looping between vertices b , c. true because our graph contains negative weight cycle.

so it's not bellman-ford doesn't correctly find shortest path.
... more accurately, there no shortest path.

[1] it's not difficult detect negative weight cycles in bellman-ford, assumes naive implementation.