Так как алгоритм Флойда последовательно релаксирует расстояния между всеми парами вершин (i,j), в том числе и теми, у которых i=j, а начальное расстояние между парой вершин (i,i) равно нулю, то релаксация может произойти только при наличии вершины k такой, что d[i][k]+d[k][i]<0, что эквивалентно наличию отрицательного цикла, проходящего через вершину i