Use Floyd-Warshall algorithm to find negative-weight circles

Question

To judge whether a graph contains negative-circles, after running the Floyd-Warshall algorithm, can I deal with the problem only by scanning the diagonal elements of the matrix to find whether it has negative elements. I dont't know how to prove it...

Answer 1

It should be clear that if there is a negative value in M[i][j] at any iteration during the algorithm then there is a path with negative cost from i to j. If M[i][i]<0 then there is a negative cost path from i toi, since it is a closed path, it must contain a cycle.

There are two cases: either **it ** is a cycle, or you can find a j different from i in the path, and partition the path into p1=path(i,j),2) p2=path(j,j) p3= path (i,j). So either p2 is a negative closed path, or p1 union p3 is a negative closed path. Take the one that is negative and apply the same argument until you do get a cycle, which must be negative

Conversely, if there is a negative cycle 'C' formed by subset of nodes S with sum of edges T, containing some node i then on the iteration in which FW has passed through all of the nodes in S, the value of M[i][i] must be at least as small as the cost of the path 'C' so M[i][i]<=T<0. Since FW is nonincreasing, M[i][i] stays negative until the end of the algorithm.