1
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\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.