We know Bellman Ford is an algorithm to find the negative cycle. And here is the algorithm for Bellman Ford Input: Given a graph G(V,E) and w(e) is weight Output: Return Yes if negative cycle exists.

1: set d(s) = 0 and d(v) = 1 for all v (- s
2: for i = 1 ... n-1 do
3:      for every edge (u, v) in G do
4:        if d(v) > d(u) + w(u,v) then
5:           d(v) = d(u) + w(u,v)
6:      end for
7: end for
8: for every edge (u, v) in G do
9:     if d(v) > d(u) + w(u, v) then
10:       return True
11:return False

Line 8 - Line 11 is the doing one more relax to detect the negative cycle, but why these lines guarantee detect the negative cycle if have one in the graph?

  • 1
    $\begingroup$ What research have you done? What textbooks/lecture notes have you read? What have you tried on your own, to try to answer this? Did you try to prove the claim yourself? Where did you get stuck? We expect you to make a serious effort to research the problem on your own before asking here. $\endgroup$ – D.W. Jun 25 '14 at 21:46

If there is a negative cycle, then it is guaranteed that $d(v)$ will decrease on each iteration for each vertex $v$ in a negative cycle, since as we do more iterations of Bellman-Ford we're considering paths that traverse that negative cycle more and more times. The more you traverse a negative cycle, the more negative the length of that path becomes. Therefore, it's guaranteed that if the graph has a negative cycle, then this algorithm will detect it, because it'll see the value of some $d(v)$ decrease.

This should be covered in standard textbooks and lecture notes on Bellman-Ford. There's not much point in having us reiterate those standard proofs again; if we don't know why you didn't understand the standard explanation, it's hard for us to write an explanation that you will help you.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.