Должно быть ясно, что если в M[i][j] есть отрицательное значение на любой итерации в течение алгоритма, то существует путь с отрицательной стоимостью от i до j. Если M[i][i]<0, то существует путь с отрицательной стоимостью от i до i, так как это закрытый путь, он должен содержать цикл.
Есть два случая: либо ** это ** цикл, либо вы можете найти j, отличный от i в пути,
и разделить путь на p1=path(i,j),2) p2=path(j,j) p3= path (i,j). Так что либо p2 - это отрицательный замкнутый путь, либо p1 union p3 - это отрицательный замкнутый путь. Возьмите отрицательный и применяйте тот же аргумент, пока не получите цикл, который должен быть отрицательным
И наоборот, если существует отрицательный цикл 'C', образованный подмножеством узлов S с суммой ребер T, содержащей некоторый узел i, то на итерации, в которой FW прошел через все узлы в S значение M[i][i] должно быть не меньше стоимости пути 'C', поэтому M[i][i]<=T<0. Поскольку FW не увеличивается, M[i][i] остается отрицательным до конца алгоритма.