Я должен найти отрицательный цикл в ориентированном взвешенном графе. Я знаю, как работает алгоритм Беллмана Форда, и что он говорит мне, существует ли достижимый отрицательный цикл. Но это явно не называет это.
Как я могу получить фактический путь цикла?
После применения стандартного алгоритма мы уже выполнили итераций, и дальнейшее улучшение не должно быть возможным. Если мы все еще можем уменьшить расстояние до узла, существует отрицательный цикл.
Моя идея такова: поскольку мы знаем ребро, которое все еще может улучшить путь, и знаем предшественника каждого узла, мы можем проследить наш путь от этого ребра, пока не встретим его снова. Теперь у нас должен быть наш цикл.
К сожалению, я не нашел ни одной бумаги, которая говорила бы мне, если это правильно. Так это на самом деле работает так?
Изменить: этот пример доказывает, что моя идея не так. Учитывая следующий график, мы запускаем Bellman-Ford из узла .
Обрабатываем ребра в порядке . После итераций мы получаем расстояния между узлами:н - 1 1 : - 5
3 : - 15
и родительская таблица: имеет родителя имеет родителя имеет родителя
3 2 3 3 2
Теперь, выполняя ю итерацию, мы видим, что расстояние до узла все еще можно улучшить с помощью ребра . Итак , мы знаем , что отрицательный цикл существует и является его частью.1 a a
Но, проследив путь через родительскую таблицу, мы застряли в другом отрицательном цикле и больше никогда не встретим .а
Как мы можем решить эту проблему?
источник
s'
иt'
). Мне казалось, что новый исходный узел, соединенный со всеми существующими вершинами ребром любой длины, развернет все циклы.Ваш пример не противоречит вашей идее. На самом деле вы нашли отрицательный цикл. Я думаю, идея, которую иллюстрирует ваш пример, состоит в том, что исходная вершина может не быть узлом в отрицательном цикле.
источник