2
$\begingroup$

Consider a graph $G$ with $N$ nodes, with the distance of each node initially set to infinity (there is no start node). If there are no negative cycles in the graph, then after $N - 1$ iterations of Bellman-Ford, any additional iterations will not modify the distances (the distances are stable).

On the other hand, if there are negative cycles in the graph, then the $N$th, $N+1$th, ... iterations will continue to decrease the distances of nodes reachable from any negative cycles in the graph.

The question is: will the $N$th (and only the $N$th) iteration relax every edge reachable from a negative cycle? That is, does it suffice to perform $N$ iterations to find all edges reachable from a negative cycle?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ If there is no start node, then there is no node with distance $0$. Then, how the distance will decrease in any iteration? all would stay infinity forever. $\endgroup$
    – Inuyasha Yagami
    Commented Jan 26 at 1:55
  • $\begingroup$ True: I meant to include that assume that the initial distances are set to some arbitrarily large value. $\endgroup$
    – dav
    Commented Jan 26 at 22:23

1 Answer 1

Reset to default
1
$\begingroup$

The following is a simple counter-example.

Let $V = \{a,b,c,d\}$ be a vertex set with all the initial distances set to arbitrarily value $D$.

There are the following directed edges with weights:

  1. $w(a,b) = -3$
  2. $w(b,c) = 1$
  3. $w(c,a) = 1$
  4. $w(b,d) = -3$

Then the edge $(b,d)$ relaxes in the $1$st, $2$nd, and $5$th iteration, and not the $4$th iteration.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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