Получение отрицательного цикла с помощью Bellman Ford

20

Я должен найти отрицательный цикл в ориентированном взвешенном графе. Я знаю, как работает алгоритм Беллмана Форда, и что он говорит мне, существует ли достижимый отрицательный цикл. Но это явно не называет это.

Как я могу получить фактический путь цикла?v1,v2,vk,v1

После применения стандартного алгоритма мы уже выполнили итераций, и дальнейшее улучшение не должно быть возможным. Если мы все еще можем уменьшить расстояние до узла, существует отрицательный цикл.n1

Моя идея такова: поскольку мы знаем ребро, которое все еще может улучшить путь, и знаем предшественника каждого узла, мы можем проследить наш путь от этого ребра, пока не встретим его снова. Теперь у нас должен быть наш цикл.

К сожалению, я не нашел ни одной бумаги, которая говорила бы мне, если это правильно. Так это на самом деле работает так?

Изменить: этот пример доказывает, что моя идея не так. Учитывая следующий график, мы запускаем Bellman-Ford из узла .1

введите описание изображения здесь

Обрабатываем ребра в порядке . После итераций мы получаем расстояния между узлами:н - 1 1 : - 5a,b,c,dn1
1:5
3 : - 152:30
3:15

и родительская таблица: имеет родителя имеет родителя имеет родителя
3 2 3 3 213
23
32

Теперь, выполняя ю итерацию, мы видим, что расстояние до узла все еще можно улучшить с помощью ребра . Итак , мы знаем , что отрицательный цикл существует и является его частью.1 a an1aa

Но, проследив путь через родительскую таблицу, мы застряли в другом отрицательном цикле и больше никогда не встретим .аc,da

Как мы можем решить эту проблему?

Патрик Шмидт
источник

Ответы:

14

Вы правы по большей части. Еще одно дополнение. Когда вы возвращаетесь к цепочке предшественников, пытаясь найти цикл, вы останавливаетесь, когда достигаете начальной вершины или любой другой вершины, которая уже была замечена в цепочке предшественников, которую вы видели до сих пор. По сути, вы останавливаете и выводите вершины всякий раз, когда обнаруживаете цикл при движении назад с использованием предшественников.v1

Что касается бумаг, простой поиск в Google дает Xiuzhen Huang: алгоритмы цикла с отрицательным весом . В качестве бонуса, они также перечисляют другой алгоритм для нахождения отрицательных циклов веса, которые не достижимы из источника вершин .s

Paresh
источник
ссылка не работает
human.js
Я просто использовал идею профессора Хуанга, но я не понимаю, почему он добавляет и новый исходный узел, и новую цель ( s'и t'). Мне казалось, что новый исходный узел, соединенный со всеми существующими вершинами ребром любой длины, развернет все циклы.
AbuNassar
0

Ваш пример не противоречит вашей идее. На самом деле вы нашли отрицательный цикл. Я думаю, идея, которую иллюстрирует ваш пример, состоит в том, что исходная вершина может не быть узлом в отрицательном цикле.

Спартанский 117
источник