# Does the Nth iteration of Bellman-Ford relax every edge reachable from a negative cycle?

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?

• 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. Commented Jan 26 at 1:55
• True: I meant to include that assume that the initial distances are set to some arbitrarily large value.
– dav
Commented Jan 26 at 22:23

Let $$V = \{a,b,c,d\}$$ be a vertex set with all the initial distances set to arbitrarily value $$D$$.
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.