# Bellman-Ford algorithm and nodes that not appear on negative cycle

Given directed graph $$G=(V,E,\omega,s,t)$$ that $$\omega:E\to \mathbb{R}$$ is the weight function on $$E$$, and we want to find shortest path from $$s$$ to $$t$$. First, we run the Bellman-Ford algorithm to finding the shortest path from $$s$$ to $$t$$, but after the termination of the algorithm, I know that if the distance of a node $$v$$ changed, then the graph contains a negative cycle that reachable from the source, so, can we conclude that $$v$$ necessarily appear in a negative cycle or not?

My attempt: I think not necessarily $$v$$ appears in a negative cycle. Consider the below example that $$t$$ not on any negative cycle, but after the termination of the algorithm, if we update the distance, its distance changed. Can we conclude that $$v$$ sometimes appears in a negative cycle or sometimes not appear on any cycle?

You are right. It doesn't mean that it will appear in a negative cycle. Rather, it means that there exists some negative cycle $$C$$ that is reachable from the source node $$s$$ and $$v$$ can be reached from $$C$$.
3. If there is a negative cycle, let $$w$$ be a node that changed in step 2
4. Do $$w\leftarrow parent(w)$$ at least $$|V|$$ times.
5. This resulting $$w$$ (after you did step 4), and all other nodes that you get by doing $$w\leftarrow parent(w)$$ (again, only after step 4. In step 4 the nodes you see don't count), have to be the negative cycle.