1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Why does the $2n$-modification fail? I think it should work just fine. $\endgroup$ – Raphael Jun 6 '14 at 10:58
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.