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?
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).
