Bellman-Ford without getting stopped by negative cycles

Question

Let $s$ be the source vertex. In the standard Bellman-Ford algorithm (e.g. the version found in CLRS), when there is a negative cycle reachable form $s$, the algorithm will return that a negative cycle is found.

But let's say I am interested in the shortest path from $s$ to some vertex $a$, and it might be that there is a negative cycle reachable from $s$, but it could also be that no such negative cycles have a path to $a$. So technically there is still a shortest path from $s$ to $a$. But Bellman-Ford would still say "negative cycle detected" although it is irrelevant! How might Bellman-Ford be modified to still spit out either the shortest path or that there is no shortest path?

Attempt: At first I saw thinking of running Bellman-Ford until $2n$ (or some large number) and then seeing if the value for $s$ to $a$ stays stable, but I found an example that invalidates this. It appears that I must find all negative cycles reachable from $s$ and check if each of them can reach $a$. That seems like an immense amount of work! So is there any clever way to do this?

Answer 1

Solution 1: First pre-process the graph to remove all vertices that cannot reach $a$. This can be done using depth-first search (backwards in the graph; i.e., in the reverse graph), in linear time. You can also pre-process the graph to remove all vertices that are not reachable from $s$, again in linear time.

Solution 2: Run Bellman-Ford for $2n$ iterations and see if the value from $s$ to $a$ stays stable for the last $n$ iterations. This should work: any simple path (with no cycle) from $s$ to $a$ must use at most $n-1$ edges, and if there is a non-simple path from $s$ to $a$ traversing a negative-weight cycle, then there is one with at most $2n-1$ edges. You might want to double-check your example; maybe you made a mistake when simulating Bellman-Ford by hand.