# If the distance to a vertex is updated in the n-th relaxation of Bellman Ford, is that vertex on a negative-weight cycle?

Recently I asked a question Here about following topics:

after finishing bellman ford algorithm, if BF continue to update distances and distance value related to one vertex v being updated,then v is on negative cycle. [***]

from my counterexample I think this is a wrong sentence.

I see in the implementation of the following problem Here That mentioned:

The key idea is that if after n−1 relaxations, there is an edge that can be relaxed further then that edge must be on a negative weight cycle.

Author says "that edge must be on a negative weight cycle".

I see also in Here that mentioned:

That is, some nodes not on the negative cycle now have a distance of negative infinity from the source because of one or more nodes on the path from the source to the node that lie in a negative cycle.

and lastly I read in comments here Comments that one user write:

All vertices that have their distances updated in the n-th phase must be on a negative weight cycle, no?

My challenge is via different statements, [***] is a correct or not correct sentence?

## 1 Answer

The statement is not correct. You can use your counter-example from before, and add redundant nodes to it.

Since the bellman-ford algorithm runs iterations equal to the number of nodes in the graph - you will see that nodes that are reachable from a negative cycle (but not on the negative cycle) will also get updated.

## The correct statement

To clear things up, here is the correct statement:

Theorem:

If a vertex $$v$$ is updated in the extra iteration of the Bellman-Ford algorithm, then there exists a negative cycle $$C$$, such that $$v$$ can be reached from $$C$$ (i.e, there is a path from any node in $$C$$ to $$v$$).

Proof:

It is well-known that a graph $$G$$ contains a negative cycle $$\iff$$ there exists some vertex that is updated in the extra Bellman-Ford iteration.

Let $$v$$ be the updated node. Then, consider the sub-graph $$G'$$ of $$G$$, consisting only of the nodes that can reach $$v$$.

Let $$d^G_{i}[u]$$ be the value given to $$u\in G$$ in the $$i$$'th iteration of the bellman ford algorithm on $$G$$, and equivalently $$d^{G'}_{i}[u]$$ on $$G'$$. Its not hard to see that for any $$u\in G'$$, $$d^{G'}_i[u]=d^{G}_i[u]$$ (i.e, the bellman-ford on $$G$$ and $$G'$$ is equivalent).

Therefore, $$v$$ must also be updated in the extra iteration if we run Bellman-Ford on $$G'$$, and thus $$G'$$ must contain a cycle $$C$$. But $$G'$$ contains only nodes that can reach $$v$$ - so it must hold that there is a path between $$C$$ and $$v$$ as required to show.