Does the 2 first algorithms we saw for APSP (matrices multiplication and Floyd Warshall) work if we have negative cycles in the graph? And if they do, how do we recognize we have a negative cycle?
Date: 03 Feb 2015 11:43
Number of posts: 4
RSS: New posts
No, no algorithm for ASPS works for negative cycles. You can always run BF first to check…
Johnson should work, shouldn't it?
It converts W to a new positive weight function so negative cycles should be eliminated
Johnson will work with negative weights, but not negative cycles.
This is because the re-weight is done using Bellman Ford which won't tollerate negative cycles.
Bellman Ford is terminated once a negative cycle is detected.