Let s be the source vertex. In the standard Bellman-Ford algorithm (e.g. the ver
ID: 651858 • Letter: L
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?
Explanation / Answer
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.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.