Skip to main content
2 of 2
added 318 characters in body

Bellman Ford Source & Negative Cycles

I’m having some troubles with Bellman Ford Algorithm in the following exerciseenter image description here

My guess is that at the end the algorithm should detect the negative cycle BD DF FG GB since B is decreasing at Vth (i.e. 7th) iteration. However changing the distance of the source does not make much sense to me. Is the source to be considered at fixed distance 0 or it can change as well as all the other vertices? Or is it correct to assume, as I did, that the algorithm will detect a negative cycle in the end?

Moreover, assuming to proceed with the computations, it is not clear to me the order I should follow. Being Vertex A not connected, should I go on relaxing from C (I guess not since it is not directly connected to B)? Or should I go on from D, which is the first vertex in alphabetic order directly connected to B? Thank you