For every $v\in V$, determine if it belongs to some negative cycle in $G$

Question

Let $G=(V,E)$ a directed graph with a weight function $w:E\to\mathbb{R}$. For every $v\in V$, determine if $v$ belongs to some negative cycle.

Obviously we need to utilize Bellman-Ford algorithm for our cause. I thought about running the first part of Bellman-Ford (looping $n-1$ times). Afterward, instead of just trying to identity a negative cycle, we scan the graph from $s$ (the source) using DFS, and checking if $d[v] > d[u] + w(u,v)$. If so, we mark $v$ as a vertex of some negative cycle.

I'd like to verify the correctness of my solution.

Thanks.

Answer 1

There are some corner cases for which your algorithm doesn't work. For example:

• What if some vertex is a part of a negative cycle unreachable from $s$ (your problem statement doesn't say anything about it, so we have to assume the worst case)?
• Your inequality might be satisfied even for vertices that are reachable from negative cycles, but doesn't belong to them.

I hope this helps $\ddot\smile$