1
$\begingroup$

The Bellman-Ford algorithm "can detect and report the negative cycle", but does it guarantee to find them or it may find some?

The algorithm really focuses on the shortest paths, so I'm unclear if it will find any negative cycle or if it might miss it.

Thanks!

EDIT: I'm only interested in knowing if there is a negative cycle (not where it is). How does one prove that Bellman-Ford would find the existence of a cycle?

$\endgroup$
1
$\begingroup$

Bellman-Ford simply returns there exists at least one negative-weight cycle, it doesn't actually find all edges part of all such cycles. At best, without extending the algorithm too much, you find at most one edge per negative-weight cycle as cycles may intersect. There are ways to recover a negative weight cycle, see the link you provided, but this is outside the scope of the Bellman-Ford algorithm.

Edit: There is a subtlety that I forgot to mention, Bellman-Ford only returns the existence of a negative-weight cycle if that is cycle is reachable from the source vertex. In a disconnected graph, it may be the case that the negative-weight cycle is unreachable, so it will not be reported. Assume therefore that for every graph with a negative-weight cycle, it is reachable from the source vertex.

The proof is fairly simple. Let $v_1, v_2, \dots, v_k, v_1$ be a reachable negative weight cycle. We assume for contradiction that $d(v_i) + w(v_i, v_{i+1}) \geq d(v_{i+1}) for all $i = 1, \dots, k$.

If we add all inequalities, we obtain

$$\sum_{i = 1}^{k} d(v_i) + \left(\sum_{i = 1}^{k - 1} w(v_i, v_{i+1}) + w(v_k, v_1)\right) \geq \sum_{i = 1}^{k} d(v_i),$$

and so $\sum_{i = 1}^{k - 1} w(v_i, v_{i+1}) + w(v_k, v_1) \geq 0$. This is a contradiction, thus it must be that there is an edge on the cycle that still can be relaxed. Note that a simple path is of at most length $|V| - 1$, and if an edge can still be relaxed after $|V| - 1$ iterations, it must be an edge of a negative-weight cycle (this is maybe a little too simplified, but the intuition is correct).

$\endgroup$
  • $\begingroup$ OK I think I understand your answer correctly but just to be sure -> if there is a negative weight cycle, Bellman-Ford will detect it right? is there a proof of this somewhere? $\endgroup$ – ben Aug 8 at 20:44
  • $\begingroup$ It tells you whether or not a negative cycle exists. It does not tell you where it is. You can easily augment Bellman-Ford to extract a negative cycle for you, but any algorithm that attempts to extract all negative simple cycles will necessarily take at least exponential total time (since there are potentially exponentially many negative simple cycles, for example in a clique). One can ask for modifications that find individual cycles with certain properties, and the complexity of that will vary depending on the sought properties. $\endgroup$ – Yonatan N Aug 8 at 21:42

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.