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

Question

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

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

    2

A-------B

      /

3    / -2

    /

    C

на сайте:

предполагая, что ребра направлены слева направо, если мы начнем
с помощью A алгоритм Дейкстры выберет минимизацию ребра (A, x)
d(A,A)+Длина (край), а именно (A,B). Затем он устанавливает d (A,B)=2 и выбирает
другой ребро (г,с) минимизации д(А,Г)+Д(Г,С); единственный выбор (а,с)
и он устанавливает 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)

}

спасибо,

Меир

1415 6

algorithm graph-algorithm shortest-path

6 ответов:

Comments

Ничего не найдено.

templatetypedef · Accepted Answer · 2014-05-10 11:18:25

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

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

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

во-первых, вы установили d(A) до zero и другие расстояния до infinity.

затем вы развернете узел A, настройка d(B) до 1,d(C) до zero и d(D) до 99.

Далее, вы расширяетесь C, без чистых изменений.

затем вы расширяетесь B, который не имеет никакого эффекта.

наконец, вы расширяете D, который меняет d(B) до -201.

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

infty10000101 · Accepted Answer · 2014-08-06 16:06:24

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

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

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

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

amit · Accepted Answer · 2011-07-23 12:07:14

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

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

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

punchoyeah · Accepted Answer · 2017-05-29 04:58:27

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

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

prusswan · Accepted Answer · 2011-07-23 12:04:39

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

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

редактировать: Я считаю, что проблема связана с тем, что путь с AC* может быть только лучше, чем AB с существованием отрицательных весовых ребер, поэтому не имеет значения, куда вы идете после AC, с предположением о неотрицательных весовых ребрах невозможно найти путь лучше, чем AB, как только вы решили достичь B после перехода ПЕРЕМЕННЫЙ ТОК.

Wackyfool · Accepted Answer · 2017-05-22 20:20:18

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

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