Алгоритм Флойда (алгоритм Флойда–Уоршелла) позволяет обнаружить отрицательные циклы в графе. 14

Процесс происходит так: алгоритм итеративно просматривает длину пути между всеми парами вершин, включая те, где i = j. 2 Изначально длина пути (i, i) равна нулю. 12 Путь [i, k, …, i] может улучшиться только в том случае, если его длина меньше нуля, то есть обозначает отрицательный цикл. 12

Чтобы найти отрицательный цикл, после завершения работы алгоритма нужно: 3

1. Найти вершину i, для которой d[i][i] < 0. 3
2. Вывести кратчайший путь между парой вершин (i, i). 3

Отрицательный цикл в графе — это цикл, сумма весов рёбер которого отрицательна. 4 Если такой цикл существует, то кратчайшего пути между некоторыми парами вершин нет, так как можно бесконечно «гулять» по циклу, уменьшая расстояние. 4