Question

1. Explain why the Floyd algorithm works even if there is negative numbers present in the distance matrix as long as we require there be no negative cycles.

Answer 1

ANSWER:
Floyd's algorithm is also known as Floyd-Warshall algorithm. It is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but no negative cycles). One execution of the algorithm will find the lengths (total weights) of the shortest paths between all pairs of vertices. Although it does not return detailed information about the paths themselves, they can be recovered using simple modifications to the algorithm.

Floyd Algorithm's working with negative numbers and negative cycles-

Negative cycle is a cycle whose edges sum to a negative value. There is no shortest path between any pair of vertices i,j that form part of a negative cycle, because the path length from i to j can be arbitrarily small (negative). For numerically significant inference, the Floyd-Warshall algorithm assumes no negative cycles. However, if there are negative cycles, the Floyd-Warshall algorithm can be used to detect them.

The important reason that Floyd algorithm works with negative numbers and not with negative cycles is that negative numbers when added with positive numbers can be used to find shortest path in a weighted graph, whereas negative cycles are not useful in finding shortest path in a graph.

If you are satisfied by my answer please give a thumbs up. Thank you.