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