Отрицательные веса с использованием алгоритма Дейкстры

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

    2
A-------B
 \     /
3 \   / -2
   \ /
    C

С веб-сайта:

Предполагая, что все ребра направлены слева направо. Если мы начнем с A, алгоритм Дейкстры выберет ребро (A, x), минимизируя d (A, A) + length (edge), а именно (A, B). Затем он устанавливает d (A, B) = 2 и выбирает другое ребро (y, C), минимизируя d (A, y) + d (y, C); единственный выбор - (A, C), и он устанавливает d (A, C) = 3. Но он никогда не находит кратчайшего пути от A до B через C с общей длиной 1.

Я не могу понять, почему при использовании следующей реализации Дейкстры d [B] не будет обновлен до 1(Когда алгоритм достигнет вершины C, он запустит расслабление на B, убедитесь, что d [B] равно 2, и, следовательно, обновите его значение 1).

Dijkstra(G, w, s)  {
   Initialize-Single-Source(G, s)
   S ← Ø
   Q ← V[G]//priority queue by d[v]
   while Q ≠ Ø do
      u ← Extract-Min(Q)
      S ← S U {u}
      for each vertex v in Adj[u] do
         Relax(u, v)
}

Initialize-Single-Source(G, s) {
   for each vertex v  V(G)
      d[v] ← ∞
      π[v] ← NIL
   d[s] ← 0
}

Relax(u, v) {
   //update only if we found a strictly shortest path
   if d[v] > d[u] + w(u,v) 
      d[v] ← d[u] + w(u,v)
      π[v] ← u
      Update(Q, v)
}

Спасибо,

Меир

Предложенный вами алгоритм действительно найдет кратчайший путь на этом графике, но не на всех графиках в целом. Например, рассмотрим этот график:

Предположим, что края направлены слева направо, как в вашем примере,

Ваш алгоритм будет работать следующим образом:

1. Во- первых, вы установили d(A)в zeroи другие расстояния до infinity.
2. Затем расшириться узел A, установка d(B)на 1, d(C)чтобы zeroи d(D)в 99.
3. Затем вы расширяетесь Cбез чистых изменений.
4. Затем вы расширяетесь B, но это не имеет никакого эффекта.
5. Наконец, вы расширяете D, который меняется d(B)на -201.

Обратите внимание, что в конце этого, тем не менее, это d(C)все еще 0, даже если у кратчайшего пути Cесть длина -200. Таким образом, в некоторых случаях ваш алгоритм не может точно вычислить расстояния. Более того, даже если бы вы сохранили обратные указатели, говорящие, как перейти от каждого узла к начальному узлу A, вы закончили бы возвращаться по неверному пути от Cк A.

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

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

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

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

вы не использовали S нигде в своем алгоритме (кроме его модификации). идея dijkstra заключается в том, что если вершина находится на S, она больше никогда не будет изменена. в этом случае, как только B окажется внутри S, вы не сможете снова добраться до него через C.

этот факт обеспечивает сложность O (E + VlogV) [в противном случае вы будете повторять ребра более одного раза, а вершины - более одного раза]

Другими словами, опубликованный вами алгоритм может не находиться в O (E + VlogV), как обещал алгоритм Дейкстры.

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

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

TL; DR: Ответ зависит от вашей реализации. Для опубликованного вами псевдокода он работает с отрицательными весами.

Варианты алгоритма Дейкстры

Ключ в том, что существует 3 варианта реализации алгоритма Дейкстры , но все ответы на этот вопрос игнорируют различия между этими вариантами.

1. Использование вложенного forцикла для расслабления вершин. Это самый простой способ реализовать алгоритм Дейкстры. Временная сложность - O (V ^ 2).
2. Реализация на основе очереди приоритетов / кучи + повторный вход НЕ разрешен, где повторный вход означает, что освобожденная вершина может быть снова помещена в очередь приоритета, чтобы ее можно было снова расслабить позже .
3. Реализация на основе очереди / кучи с приоритетом + повторный вход разрешен.

Версии 1 и 2 не будут работать на графиках с отрицательными весами (если вы получите правильный ответ в таких случаях, это просто совпадение), но версия 3 по-прежнему работает .

Псевдокод, опубликованный под исходной проблемой, - это версия 3 выше, поэтому он работает с отрицательными весами.

Вот хорошая ссылка из алгоритма (4-е издание) , в котором говорится (и содержится java-реализация версий 2 и 3, о которых я упоминал выше):

В. Работает ли алгоритм Дейкстры с отрицательными весами?

А. Да и нет. Существует два алгоритма кратчайших путей, известных как алгоритм Дейкстры, в зависимости от того, может ли вершина быть поставлена ​​в очередь приоритетной очереди более одного раза. Когда веса неотрицательны, две версии совпадают (поскольку ни одна вершина не будет помещена в очередь более одного раза). Версия, реализованная в DijkstraSP.java (которая позволяет ставить вершину в очередь более одного раза), верна при наличии отрицательных весов ребер (но без отрицательных циклов), но время ее работы в худшем случае экспоненциально. (Заметим, что DijkstraSP.java выдает исключение, если взвешенный по ребрам орграф имеет ребро с отрицательным весом, так что программист не удивится этому экспоненциальному поведению.) Если мы изменим DijkstraSP.java так, чтобы вершина не могла быть поставлена ​​в очередь более одного раза (например, используя массив отмеченных [], чтобы отметить те вершины, которые были ослаблены),

Дополнительные сведения о реализации и связи версии 3 с алгоритмом Беллмана-Форда см. В этом ответе от zhihu . Это тоже мой ответ (но на китайском). Сейчас у меня нет времени переводить его на английский. Я очень признателен, если бы кто-то мог это сделать и отредактировать этот ответ в stackoverflow.

Подумайте, что произойдет, если вы будете перемещаться между B и C ... вуаля

(актуально, только если граф не направлен)

Отредактировано: я считаю, что проблема связана с тем фактом, что путь с AC * может быть лучше, чем AB, с существованием ребер с отрицательным весом, поэтому не имеет значения, куда вы пойдете после AC, с предположением отсутствия ребра с отрицательным весом невозможно найти путь лучше, чем AB, если вы решили достичь B после перехода AC.

«2) Можем ли мы использовать алгоритм Дейксры для поиска кратчайших путей для графов с отрицательными весами - одна идея может заключаться в том, чтобы вычислить минимальное значение веса, добавить положительное значение (равное абсолютному значению минимального значения веса) ко всем весам и запустить алгоритм Дийксры для модифицированного графа. Будет ли работать этот алгоритм? "

Это абсолютно не работает, если все кратчайшие пути не имеют одинаковой длины. Например, дан кратчайший путь длиной два ребра и после добавления абсолютного значения к каждому ребру общая стоимость пути увеличивается на 2 * | max отрицательный вес |. С другой стороны, другой путь длиной три ребра, поэтому стоимость пути увеличивается на 3 * | max отрицательный вес |. Следовательно, все отдельные пути увеличиваются на разную величину.

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

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