Изменения

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