The Floyd-Warshall algorithm fails (does not work correctly) if the input graph has a negative weight cycle.
Fantastic news! We've Found the answer you've been seeking!
Question:
The Floyd-Warshall algorithm fails (does not work correctly) if the input graph has a negative weight cycle.
(a) Draw a small graph with a negative-weight cycle. Demonstrate the result of running Floyd-Warshall on it (show D(k) for k = 1, . . . , n).
(b) In general, how can you use the output of the Floyd-Warshall algorithm to detect the presence of a negative-weight cycle?
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date: