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

Question

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

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

С веб-сайта:

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

Я не могу понять, почему при использовании следующей реализации Dijkstra 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)
}

Спасибо,

Меир

Answer 1

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

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

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

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.

Answer 2

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

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

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

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

Answer 3

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

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

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

Answer 4

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

---

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

Answer 5

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

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

Answer 6

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

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

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

Answer 7

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

---

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

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

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

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

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

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

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

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

---

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