Изменения

:Приведенная выше реализация позволяет определить наличие в графе цикла отрицательного веса. Чтобы найти сам цикл, достаточно сохранять массив вершин из которых производится релаксация. Тогда, если после <tex> \mid V \mid - 1 </tex> итерации найдется вершина <tex> v </tex>, расстояние до которой можно уменьшить, то эта вершина либо лежит на каком-нибудь цикле отрицательного веса, либо достижима из него. Чтобы найти вершину, которая лежит на цикле, можно <tex>\mid V \mid - 1</tex> раз пройти назад по предкам из вершины <tex> v </tex>. Так как наибольшая длина пути в графе из <tex>\mid V \mid</tex> вершин равна <tex>\mid V \mid - 1</tex>, то полученная вершина <tex> u </tex> будет гарантированно лежать на отрицательном цикле. Теперь, зная что вершина <tex> u </tex> лежит на цикле отрицательного веса, можно пройти из нее по предкам, пока не придем в эту ту же вершину <tex> u </tex>, а это . Это обязательно произойдет, так как в цикле отрицательного веса релаксации происходят по кругу.