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

Question

Что делать, если единственные отрицательные пограничные издержки исходят от начального узла?Будет ли алгоритм все еще работать?

Мне кажется, что да, потому что я не могу придумать контрпример, но мне трудно доказать это.Есть ли контрпример?

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

Я не ищу алгоритм.Я ищу некоторое понимание Дейкстры.

Я говорю о ориентированном графе, если это имеет значение.

Answer 1

Проблема с отрицательным преимуществом заключается в том, что вы можете перемещаться по нему столько раз, сколько захотите.

Если вы вводите правило, что преимущество не может использоваться более одного раза, у вас все еще есть проблема.Алгоритм Дейкстры включает в себя маркировку узла как «посещенного», когда его расстояние от начального узла считается известным раз и навсегда.Это происходит до того, как все края были изучены;кратчайший путь от начального узла к узлу X найден, все остальные пути от начального узла уже длиннее этого, ничто из обнаруженного позже не сможет сделать эти пути короче .Но если где-то есть ребра с отрицательной стоимостью, то позднее открытие может сделать путь короче, поэтому может случиться так, что существует более короткий путь, который Дейкстра не обнаружит.

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

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

1. Итак, возьмите свой график, назовите его A , найдите наименьшую стоимостьлюбое ребро, соединенное с начальным узлом, назовите его k, что в этом случае будет отрицательным).
2. Создайте новый график B , который вы получите, вычтя k из стоимости каждого ребра, соединенного с начальным узлом.Обратите внимание, что все эти затраты теперь неотрицательны.Так Дейкстра работает на B .Также обратите внимание, что кратчайший путь в B также является кратчайшим путем в A .
3. Назначьте начальному узлу B расстояние k, затем запустите Dijkstra (это даст тот же путь, что и бег с начальным расстоянием, равным нулю).Сравните это с наивным запуском Dijkstra на A : как только вы покидаете начальный узел , на двух графиках все одинаково.Расстояния одинаковы, решения одинаковы, оба будут давать один и тот же путь.А в случае A расстояние будет правильным, так как оно началось с нуля.

Answer 2

Counter-пример:

График G = (V, E), с вершинами V = {A, B}, ребрами E = {(A, B), (B, A)} и весовой функцией w (A, B) = -2 , ш (В, А) = + 1.

Существует отрицательный весовой цикл, поэтому минимальные расстояния не определены (даже при использовании A в качестве начального узла).

Answer 3

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

A -> B : 6
A -> C : 5
B -> D : 2
B -> E : 1
D -> E : -5
E -> C : -2