0
$\begingroup$

I recently started studying algorithms on my own using Cormen and MIT algo videos in YouTube. I am going thru Bellman-Ford.

enter image description here

I have 2 doubts about the correctness of the algorithm:

  1. Why are we relaxing (num of vertices - 1) times all the edges? Why not some finite number of times till earlier values and new values remain same?

  2. The second for loop (lines 5,6,7 in algo image) is for detecting negative edge cycles. Then I have gone through this correctness. I have seen a theorem that if there is a negative edge cycle reachable from source s then we can find an edge uv such that d(v)>d(u)+w(u,v) [I understood the proof by contradiction (if summing all vertices of negative edge cycle results in sum of all weights along negative cycle positive which means contradiction as it must be negative - page 2 of https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture14.pdf]

But I am not able to visualise such an edge if I have some negative edge cycle from source vertex s. Please help me: how can such an edge exist?

enter image description here

Improve this question
$\endgroup$
3
$\begingroup$

If there are no negative cycles then you can indeed perform the relaxation until all values remain the same. In the $i$-th round of relaxation you are ensured to have correctly computed all finite distances towards all vertices whose hop-distance from $s$ is at most $i$ (the hop distance is the number of edges in a shortest path).

Therefore stopping after the $(n-1)$-th iteration ensures that:

  • All finite distances have been correctly computed
  • The algorithm terminates on graphs with negative cycles.

Notice that there are graphs where all $(n-1)$ iterations are needed to properly compute the distances. E.g., a path.

Regarding 2), your question is not completely clear to me. In the proof there is no particular edge to visualize. The proof just shows that if it impossible for these two conditions to be simultaneously true:

  • There is some negative weight cycle $C$.
  • No relaxation happens, i.e., $v.d \le u.d + w(u,v)$ for all vertices $v$ of the cycle. This is used in the second centered inequality.
Improve this answer
$\endgroup$
7
  • $\begingroup$ sir part 1 i understood now clearly. In 2nd part (algo in the image i posted - lines 5,6,7 detect negative edge cycle). In pdf link, there is lemma that - if there is a negative cycle reachable from source s then thre is some edge u,v such that d[v]>d[u]+w[u.v]. can u pls give me an example of such edge ? i am not able to visualise even though i understood that proof part. $\endgroup$
    – Nascimento de Cos
    Jun 9 '20 at 8:09
  • $\begingroup$ I read the proof you linked and I did not find such a lemma. Can tell me where it is, exactly? $\endgroup$
    – Steven
    Jun 9 '20 at 8:13
  • $\begingroup$ sir pls see above image. Its in page 2 - point number 1 (just below algo) in that stanford pdf $\endgroup$
    – Nascimento de Cos
    Jun 9 '20 at 8:27
  • 1
    $\begingroup$ Consider the graph with $n=3$ vertices, vertex set $\{s,a,b\}$, edge set $\{ (s,a), (a,b), (b,s) \}$ (a triangle), and edge weights $w(s,a)=w(s,b)=1$, $w(a,b)=-3$. After $2=n-1$ iterations of Bellman ford that examine edges in the same order as they are listed above, you have $d(s)=-2$, $d(a)=0$, $d(b)=-3$. An edge $(u,v)$ such that $d(v) \ge d(u) + w(u,v)$ is $(b,s)$ since $-2 = d(s) \ge d(b) + w(b,s) = -3 - 3 = - 6$. $\endgroup$
    – Steven
    Jun 9 '20 at 9:05
  • $\begingroup$ sir i understood now. But sir it should be [s,a]; d(a)=0; d(s)+w(s,a)=(-2)+1=(-1); 0=d(a)>(-1); w(b,s) = 1 and not -3. $\endgroup$
    – Nascimento de Cos
    Jun 9 '20 at 9:37

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.