Алгоритм цикла с отрицательным весом

Question

Я думал об алгоритме нахождения отрицательного весового цикла в ориентированном графе. Проблема в том, что у нас есть граф G (V, E), нам нужно найти эффективный алгоритм, чтобы найти цикл с отрицательным весом. Я понимаю алгоритм в этом документе PDF

Вкратце, алгоритм применяет алгоритм Беллмана Форда, повторяя | V | -1 раз, делая релаксации. После этого он проверяет, есть ли ребро, которое можно даже ослабить больше, затем существует отрицательный весовой цикл, и мы можем проследить его по родительским указателям, и все идет хорошо, мы находим отрицательный весовой цикл.

Тем не менее, я думал о другом алгоритме - просто использовать поиск по глубине (DFS) на графике, отслеживая сумму до пройденных вами расстояний, я отмечаю все узлы белыми в начале и делаю их серыми когда я ищу путь и помечаю их черным, когда они закончены, я знаю, что нахожу цикл тогда и только тогда, когда нахожу посещенный узел, и он серый (на моем пути), а не черный, который уже был закончен с помощью поиска в глубину и, таким образом, для моего алгоритма, если я достигну серого узла, который уже был посещен, я проверяю, каким будет его обновление (новое расстояние), и если оно ниже, чем раньше, я знаю, что у меня есть отрицательный весовой цикл и может проследить его обратно.

Мой алгоритм неверен? Если да, можете ли вы найти контрпример? Если нет, можете ли вы помочь мне доказать это?

Спасибо

Answer 1

Беллман Форд не всегда работает, проблема в том, что его алгоритм кратчайший путь с одним источником , если отрицательный цикл недоступен из выбранного вами источника, он терпит неудачу.Однако небольшое изменение в Bellman Ford может помочь, вместо выбора исходной вершины и инициализации ее расстояния до 0, мы можем инициализировать все расстояние до 0 и затем запустить Bellman Ford.Это эквивалентно добавлению дополнительной вершины s ', которая указывает на все вершины исходного графа с нулевым ребром веса.Как только Беллман Форд будет запущен на графе, и мы найдем любую вершину u и ребро (u, v), которые делают d [u] + w [u] [v]

DFS не будет работать никоим образом, очевидно, он не сможет исчерпать все возможные циклы.С помощью DFS можно найти наличие цикла на графике, но не более.

Answer 2

Одна очевидная проблема - вы отмечаете узлы.

 A <--->   B
 |         ^ 
   \--\    |  
           v    
       ->  D  (crap ascii art, A  connects to D unidirectionally)

Предположим, вы выбрали путь A-> B-> D, ABD серого цвета, когда вы нажали D. Цикл не найден.Вы всплываете к А;B и D черные.Вы берете край, цикл не найден, потому что D черный.

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

Answer 3

Я считаю, что есть способ решить это за линейное время. При поиске в графе с помощью поиска в глубину (DFS имеет время выполнения O (V + E)), вы можете отслеживать расстояние от источника до текущего узла (просто увеличивая расстояние родителя с весом ребро, соединяющее дочерний узел с родительским). Затем, всякий раз, когда вы сталкиваетесь с циклом (циклы обнаруживаются путем нахождения заднего ребра в неориентированном графе или либо заднего ребра, либо переднего ребра в ориентированном графе), вы можете вычесть расстояние между исходным узлом и корневой узел цикла от расстояния между исходным узлом и конечным узлом в цикле (корневой узел является узлом, где начался цикл). Если результат отрицательный, цикл должен быть отрицательным!