В чем заключается алгоритм Беллмана-Форда для поиска отрицательных циклов?

Алгоритм Беллмана-Форда для поиска отрицательных циклов позволяет проверить наличие или отсутствие цикла отрицательного веса в графе, а при его наличии — найти один из таких циклов. 5

Работа алгоритма заключается в следующем: 5

1. Делается итерация алгоритма Беллмана-Форда. 5 Если на последней итерации не произошло никаких изменений, то отрицательного цикла в графе нет. 5
2. В противном случае берётся вершина, расстояние до которой изменилось, и от неё идут по предкам, пока не войдут в цикл. 5 Этот цикл и будет искомым отрицательным циклом. 5

Алгоритм Форда-Беллмана позволяет найти кратчайшие пути из одной вершины графа до всех остальных, даже для графов, в которых веса рёбер могут быть отрицательными. 2