Bellman Ford Source & Negative Cycles

Question

I’m having some troubles with Bellman Ford Algorithm in the following exercise

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

Answer 1

The source distance does not need to be treated specially. It can change like any other vertex. In this scenario, it'll be updated to -1 by the end of the fourth round. The weights into and out of B will never become quiescent: either B's distance will be more than 2 greater than G's distance, or (say) A's distance will be more than 5 greater than B's distance. So the cycle will still be detected.

Now, if you ever find yourself reducing the source distance below zero, you immediately know that there's a negative cost cycle, and can terminate early. But there's no need to do so for the algorithm to work.