Vertices reachable from negative-weight cycles in Bellman-Ford

Question

TLDR: I want to know if there's a simple way to fill in distances for all vertices reachable from negative weight cycles (not just ones on the cycle itself) once Bellman-Ford has found a negative-weight cycle.

The Bellman-Ford algorithm finds single-source shortest distances $d$ for a graph of $|V|$ vertices by making $|V|-1$ passes through all $|E|$ edges with weights $w$, and then checking each edge $u \rightarrow v$, with weight $w(u,v)$, for negative-weight cycles. If $v.d > u.d + w(u,v)$, then we know that there exists a negative weight cycle consisting of some path from $v$ to $u$, then the edge $(u,v)$. It's straightforward to find every vertex on that cycle and set all their $d$ to $-\infty$.

However, this also must mean that any vertices reachable from but not on this cycle must also have $d = -\infty$. One way to update all their distances is to collapse each cycle to a vertex and then perform DFS from each such "cycle vertex", setting $x.d = -\infty$ for every reachable vertex $x$.

I'm wondering if there's a faster way to update all the distances, involving perhaps a smaller modification to Bellman-Ford?

Answer 1

You don't need to perform DFS separately from each such vertex. Instead, add a new fake vertex $s_0$, with an edge from $s_0$ to each vertex in a negative cycle; use DFS to find all vertices reachable from $s_0$; and set their distances to $-\infty$. This needs only a single DFS, rather than many DFS's. It is simple and fast; there is no hope for something that is asymptotically faster, as it takes linear time, and in the worst case, you might need to visit all vertices, taking linear time in the worst case.