Работает ли алгоритм Дейкстры с отрицательными ребрами, если нет «обработанной» проверки?

Question

Как правило, в алгоритме Дейкстры для каждого обнаруженного узла мы проверяем, был ли обработан этот узел, прежде чем пытаться обновить расстояния своих соседей и добавлять их в очередь. Этот метод предполагает, что, если расстояние до узла установлено один раз, то расстояние до этого узла не может улучшиться для остальной части алгоритма, и поэтому, если узел уже был обработан один раз, тогда расстояния до его соседей не могут улучшиться. Однако это не так для графов с отрицательными ребрами.

Если нет отрицательных циклов, то если мы уберем эту «обработанную» проверку, то будет ли алгоритм всегда работать для графов с отрицательными ребрами?

Редактировать: пример графика, где алгоритм потерпит неудачу, было бы неплохо

Редактировать 2: Java код https://pastebin.com/LSnfzBW4

Пример использования:

3 3 1 <-- 3 nodes, 3 edges, starting point at node 1
1 2 5 <-- edge of node 1 and node 2 with a weight of 5 (unidirectional) 
2 3 -20 <-- more edges
1 3 2

Answer 1

Алгоритм даст правильный ответ, но поскольку узлы теперь можно посещать несколько раз, временная сложность будет экспоненциальной.

Вот пример, демонстрирующий экспоненциальную сложность:

w(1, 3) = 4
w(1, 2) = 100
w(2, 3) = -100
w(3, 5) = 2
w(3, 4) = 50
w(4, 5) = -50
w(5, 7) = 1
w(5, 6) = 25
w(6, 7) = -25

Если алгоритм пытается найти кратчайший путь от узла 1 к узлу 7, он сначала достигнет узла 3 через ребро с весом 4, а затем исследует оставшуюся часть графика. Затем он найдет более короткий путь к узлу 3, сначала перейдя к узлу 2. Затем он снова исследует оставшуюся часть графика.

Каждый раз, когда алгоритм достигает одного из нечетных индексированных узлов, он будет сначала go к следующему нечетному индексируемому узлу через прямое ребро и исследуйте остальную часть графика. Затем он найдет более короткий путь к следующему нечетному индексированному узлу через четный индексированный узел и снова исследует оставшуюся часть графика. Это означает, что каждый раз, когда достигается один из нечетных индексированных узлов, остальная часть графика будет исследована дважды, что приведет к сложности не менее O(2^(|V|/2)).

Answer 2

Если я правильно понимаю ваш вопрос, я не думаю, что это возможно. Без обработанной проверки алгоритм попадет в бесконечное число l oop. Например, для двунаправленного графа, имеющего два узла, то есть a и b с одним ребром от «a» до «b» или от «b» до «a», он сначала вставит узел «a» в очередь с приоритетами, затем по мере иметь ребро между "a" и "b", оно вставит узел "b" и поп-узел "a". И тогда, когда узел "a" не помечен как обработанный для узла "b", он снова вставит узел "a" в очередь с приоритетами и так далее. Что приводит к бесконечности l oop.

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

Answer 3

Если отрицательные ребра освобождаются от начального узла, алгоритм Дейкстры работает. Но в другой ситуации Обычно это не работает для отрицательных граней.