Может ли кто-нибудь меня понять, почему эта реализация алгоритма dijkstra не работает для отрицательных весов?

Question

Я посмотрел на реализацию алгоритма dijkstra found here, но, похоже, он отлично работает для отрицательных весов.

В частности, метод relax обновляет расстояние вершины в очереди приоритетов или вставляет его обратно, если он не был первоначально в очереди.

И поскольку нет никаких проверок, чтобы убедиться, что мы не вставляем уже известную вершину, не будет ли эта реализация более похожей на алгоритм bellman-ford, где мы продолжаем вставлять вершины, чтобы посещать и расслабляться, пока не закончится краев, которые уменьшают расстояние?

Например:

При запуске его на изображении ниже с А в качестве источника, мы сначала определить следующие расстояния:

C = 0 
B = 1 
D = 99 

Затем после наших удалений очереди, мы остались с (D , 99), что заставляет нас посетить вершину D и расслабить ее. При ослаблении вершины D получаем, что (от D до B = -300), что делает расстояние до B равным -201. Теперь, используя вышеописанный метод «расслабиться», мы снова вставляем (B, -201) в очередь. Теперь мы берем min очереди, которая является (B, -201), которую мы только что вставили. Из этого мы расслабляем B, и мы можем получить расстояние до C до -200.

Я знаю, что любой отрицательный цикл сделает программа не завершается, но что, если задан график, без отрицательного цикла? Надеюсь, у меня здесь нет ничего тривиального. Спасибо за любую помощь!

Answer 1

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

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

---

Причина, по которой автор выдает исключение, заключается в том, что он не хочет обрабатывать «недействительный» график и особенно бесконечные циклы.

---

PS: Ваш конкретный график на самом деле ДОЛЖНА быть разрешимы Дейкстры, но представьте себе, этот граф с отрицательным фронтом и нет циклов:

A ->(1) B ->(1) -> C 
|  (-300) 
v  ^
(5)  | 
D ->(1) E 

Вы на самом деле решить

B=1 
C=2 

И после этого вы ЗАКРЫВАЕТ A, B и C и не хотите вводить их снова. Но после этого вы обнаружите, что A-> D-> E-> B - -294, а затем вы повторно вводите все остальные значения.

Чтобы понять, почему это так плохо, я дам вам еще один пример

A ->(1) B ->(1) -> C -> SUPERGRAPH 
    | (-999999) 
    v  ^
    (99999) | 
    D ->(1) E 

Так что теперь A-> D является чрезвычайно высокое значение и C указывает на какой-то надграфиком, которые, однако, не переходят 99999 в общей сложности «длина» от A.

Что происходит? Даже если это работает, и нет других циклов, вы решаете весь суперграф от A, но после этого вы обнаружите, что на самом деле A-> B намного короче, и вам нужно снова решить всю SUPERGRAPH. Если у вас больше подобных ситуаций, для каждого из них вам нужно снова запустить Dijkstra alghoritm.

Answer 2

Потому что, если вы положили в отрицательном весе он будет throw new IllegalArgumentException("edge " + e + " has negative weight");