Floyd Warshall Dynamic Programming

Can Floyd Warsahll algorithm be applicable with cycles of negative length ??
@kcahdog @vineetpaliwal @anton_lunyov @darkshadows @hkbharath Please help me out with this problem.Thanx in advance :slight_smile:

Hi,

Floyd-Warshall can NOT be applied if there are cycles whose weight is negative. There is no shortest path between any pair of vertices i, j which form part of a negative cycle, because path-lengths from i to j can be arbitrarily small (negative). For numerically meaningful output, the Floyd–Warshall algorithm assumes that there are no negative cycles. Nevertheless, if there are negative cycles, the Floyd–Warshall algorithm can be used to detect them.

However, you can have edges with positive or negative weight and the algorithm still works correctly as long as there’s not a negative weight cycle.

Best,

Bruno

2 Likes

@kuruma thanx for the info :slight_smile:

@adijimmy, you’re welcome :slight_smile: Also, if you think this helped you out, please mark answer as Accepted so thread can be closed. Meanwhile, thanks for the upvote

//