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

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

    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. Но он никогда не находит кратчайший путь от А до 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)
}

Спасибо,

Меир

Ответы

Ответ 1

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

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

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

Сначала вы установите d(A) на zero, а остальные расстояния - на infinity.
Затем вы разверните node A, установив d(B) на 1, d(C) на zero и d(D) на 99.
Затем вы разворачиваете C без изменений в сети.
Затем вы разверните B, который не имеет эффекта.
Наконец, вы расширяете D, который меняет d(B) на -201.

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

Ответ 4

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

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

Ответ 5

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

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

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

Ответ 6

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

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

Ответ 7

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

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

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

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

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

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

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

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

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

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