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

113

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

    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)
}

Спасибо,

Меир

Меир
источник
В общем, поиск пути с отрицательным весом ребер чрезвычайно труден. Независимо от того, какой маршрут вы найдете, всегда существует возможность произвольно длинного маршрута с произвольно большим отрицательным весом ребра где-то на его протяжении. Я не удивлюсь, если это полная NP.
Ник Джонсон
4
Для всех, кто сомневается в этом, вы можете найти кратчайший путь в графике, ДАННЫЙ, что он не имеет циклов отрицательного веса. Вышеупомянутый алгоритм работал бы, если бы функция Relax возвращала значение «true», когда релаксация была фактически успешной, и в этом случае смежная вершина «v» будет помещена в очередь приоритета, если отсутствует, или обновлена, если уже присутствует. Это означает, что посещенные узлы могут снова быть добавлены в очередь приоритетов, поскольку они продолжают расслабляться.
goelakash

Ответы:

203

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

Рисунок графика

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

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

  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
источник
35
Чтобы добавить к своему превосходному ответу: Жадный алгоритм Дейкстры является причиной его недальновидного выбора.
blubb
4
Я хотел бы отметить, что технически все пути в этом графике имеют стоимость отрицательной бесконечности благодаря отрицательному циклу A, D, B, A.
Nate
2
@ Nate - Чтобы уточнить, все ребра в графе направлены слева направо. Рендерить стрелки в моем высококачественном ASCII-графике было довольно сложно. :-)
templatetypedef
2
Для тех, кто раньше не видел графов с отрицательными ребрами, я считаю полезной интерпретацию этого графа как сеть платных дорог, где веса ребер дают плату за проезд. Дорога -300 - это сумасшедшая платная дорога в обратном направлении, где вместо этого вам дают 300 долларов.
D Coetzee
3
@ SchwitJanwityanujit - Так работает алгоритм Дейкстры. Алгоритм не исследует пути , а работает через узлы обработки . Каждый узел обрабатывается ровно один раз, поэтому, как только мы обработаем узел B и получим, что его расстояние равно 1, мы никогда не будем повторно посещать узел B или пытаться обновить его расстояние.
templatetypedef
25

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

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

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

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

infty10000101
источник
2. Непонятно, почему вы думаете, что время будет мне «больше похоже на Беллмана-Форда», а не экспоненциально (что хуже, чем Беллман-Форд). У вас есть конкретный алгоритм и доказательство?
Gassa 06
3
К 1.: поскольку вы можете использовать точно такую ​​же реализацию dijkstra с упомянутым критерием остановки, которая останавливается, когда очередь пуста (см. Псевдокод в исходном вопросе), это все еще алгоритм dijkstras для кратчайших путей, хотя он ведет себя по-другому установка узлов несколько раз (корректировка метки).
infty10000101 06
1
To 2 .: Это было только предположение, поэтому я собираюсь удалить это. Я думаю, что вы правы в отношении экспоненциального времени, поскольку существует экспоненциально много путей, которые необходимо изучить.
infty10000101
11

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

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

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

амит
источник
Кроме того, нет необходимости изменять вершину без ребер с отрицательным весом, что полностью разрушает предположение о том, что стоимость пути может увеличиваться только с повторением ребер
prusswan
именно это предположение позволяет нам использовать S, и «зная», что когда вершина находится в S, она больше никогда не будет изменена.
amit
Ваше последнее утверждение неверно. Опубликованный алгоритм имеет временную сложность O (E + VlogV) при работе на графах без отрицательных ребер. Нет необходимости проверять, что мы уже посетили узел, поскольку тот факт, что он был посещен, гарантирует, что процедура релаксации не добавит его еще раз в очередь.
Pixar,
7

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


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

пунхоа
источник
4

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.

соло
источник
1

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

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

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

prusswan
источник
это невозможно, график ориентирован.
amit
@amit: хороший момент, я это пропустил. Время пересмотреть проблему
prusswan
1

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

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

Дурачок
источник
0

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

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

CodingLab
источник