Почему алгоритм Дейкстры не работает для ребер с отрицательным весом?

121

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

Я говорю только о ребрах, а не о циклах с отрицательным весом.

Маду
источник
3
Правильный ответ с хорошим примером: stackoverflow.com/questions/6799172/…
Amitk

Ответы:

175

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

Но с отрицательными весами - это может быть неправда. Например:

       A
      / \
     /   \
    /     \
   5       2
  /         \
  B--(-10)-->C

V={A,B,C} ; E = {(A,C,2), (A,B,5), (B,C,-10)}

Дейкстра из A сначала разработает C, а потом не сможет найти A->B->C


ИЗМЕНИТЬ немного более глубокое объяснение:

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

Идея такова: если у нас есть открытая вершина, стоимость которой минимальна - путем добавления любого положительного числа к любой вершине - минимальность никогда не изменится.
Без ограничения на положительные числа - вышеприведенное предположение неверно.

Поскольку мы «знаем», что каждая вершина, которая была «закрыта», минимальна - мы можем безопасно выполнить шаг релаксации - не «оглядываясь назад». Если нам действительно нужно «оглянуться назад» - Bellman-Ford предлагает рекурсивное решение (DP) для этого.

Амит
источник
5
Извините, но я не получаю никаких сообщений об ошибках. Сначала A->Bбудет 5 и A->Cбудет 2. Потом B->Cбудет -5. Значит, стоимость Cбудет -5такая же, как у беллмана-форда. Как это неправильный ответ?
Анирбан Наг 'tintinmj'
5
Сначала @tintinmj, Дейкстра "закроет" узел Aсо значением 0. Затем он будет смотреть на узле с минимальным значением, равным B5 и C2. Минимальным является C, поэтому он закроется Cсо значением 2 и никогда не будет оглядываться назад, когда позже Bзакрывается, он не может изменять значение C, так как он уже "закрыт".
amit
4
@amit Как алгоритм Дейкстры не находит путь A -> B -> C? Сначала он обновит Cрасстояние до 2, а затем Bрасстояние до 5. Предполагая, что в вашем графе нет исходящих ребер C, мы ничего не делаем при посещении C(и его расстояние по-прежнему равно 2). Затем мы посещаем Dсоседние узлы, и единственный соседний узел - это Cновое расстояние -5. Обратите внимание, что в алгоритме Дейкстры мы также отслеживаем родительский элемент, из которого мы достигаем (и обновляем) узел, и, выполняя это C, вы получите родительский элемент B, а затем получите Aправильный результат. Что мне не хватает?
nbro
12
@amit Проблема с вашими рассуждениями (я думаю), и я видел, как другие люди делали это (как ни странно), заключается в том, что вы думаете, что алгоритм не будет пересматривать узлы, кратчайшее расстояние которых уже определено (и с которыми мы закончили), но это неверно, и поэтому у нас есть шаг "расслабления" ... Мы перебираем все узлы графа, и для каждого из них мы перебираем соседние узлы, даже если любой из соседних узлов может например, уже были удалены из нашей очереди с минимальным приоритетом.
nbro
10
@amit Отметьте этот ответ на аналогичный вопрос, где пример действительно имеет смысл: stackoverflow.com/a/6799344/3924118
nbro
37

Рассмотрим график, показанный ниже, с источником как Вершина A. Сначала попробуйте самостоятельно запустить на нем алгоритм Дейкстры.

введите описание изображения здесь

Когда я ссылаюсь на алгоритм Дейкстры в своем объяснении, я буду говорить об алгоритме Дейкстры, реализованном ниже,

Алгоритм Дейкстры

Итак, начальные значения ( расстояние от источника до вершины ), изначально присвоенные каждой вершине, следующие:

инициализация

Сначала мы извлекаем вершину в Q = [A, B, C], которая имеет наименьшее значение, то есть A, после чего Q = [B, C] . Обратите внимание, что A имеет направленное ребро к B и C, также оба они находятся в Q, поэтому мы обновляем оба этих значения,

первая итерация

Теперь извлекаем C как (2 <5), теперь Q = [B] . Обратите внимание, что C ни к чему не подключен, поэтому line16цикл не выполняется.

вторая итерация

Наконец, мы извлекаем B, после чего Q - это Фи. Обратите внимание, что B имеет направленное ребро к C, но C отсутствует в Q, поэтому мы снова не вводим цикл for line16,

Третий?

Таким образом, мы получаем расстояния как

без изменений, ребята

Обратите внимание, насколько это неверно, поскольку кратчайшее расстояние от A до C составляет 5 + -10 = -5, когда вы идете от а до б до с.

Итак, для этого графа алгоритм Дейкстры неверно вычисляет расстояние от A до C.

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

То , что line16петля делает, принимая вершину U и сказать : «Эй , похоже , что мы можем пойти против от источника через U , что (альт или альтернатива) расстояние лучше , чем текущий дист [v] мы получили? Если так давайте обновление dist [v] "

Обратите внимание , что в line16они проверяют все соседи V (то есть направленное ребро существует от U до V ), из U которые еще в Q . В line14них удалить посещенную заметку из Q. Таким образом , если х является посещаемым соседом U , путь источник к u к xбудет даже не рассматриваются как возможный короткий путь от источника к V .

В нашем примере выше C был посещенным соседом B, поэтому путь От А до Б до Сне учитывался, оставив текущий кратчайший путь От А до Снеизменным.

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

Поэтому я говорю, что при запуске этого алгоритма, если x извлекается из Q до y , то невозможно найти путь - невозможнокоторый короче. Позвольте мне объяснить это на примере,

Поскольку y только что был извлечен, а x был извлечен перед собой, тогда dist [y]> dist [x], потому что иначе y был бы извлечен до x . ( line 13сначала минимальное расстояние)

И как мы уже предполагали, что веса ребер положительны, то есть length (x, y)> 0 . Таким образом, альтернативное расстояние (alt) через y всегда будет больше, т.е. dist [y] + length (x, y)> dist [x] . Таким образом, значение dist [x] не было бы обновлено, даже если бы y рассматривался как путь к x , таким образом, мы заключаем, что имеет смысл рассматривать только соседей y, которые все еще находятся в Q (обратите внимание на комментарий в line16)

Но это зависит от нашего предположения о положительной длине ребра, если length (u, v) <0, то в зависимости от того, насколько отрицательным является это ребро, мы можем заменить dist [x] после сравнения в line18.

Таким образом, любое вычисление dist [x], которое мы сделаем, будет неверным, если x будет удален до того, как будут удалены все вершины v - такие, что x является соседом v с отрицательным ребром, соединяющим их.

Поскольку каждая из этих v вершин является второй последней вершиной на потенциально «лучшем» пути от источника до x , который отбрасывается алгоритмом Дейкстры.

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

Чтобы уточнить, B и C - соседи A. B имеет одного соседа C, а C не имеет соседей. length (a, b) - длина ребра между вершинами a и b.

Адитья П.
источник
2
Как вы сказали, лучший способ решить эту проблему - использовать метод heapq.heappush после каждого сравнения. Отодвигаем обновленное расстояние в очередь. При этом условии Дейкстры могут работать с отрицательными весами. Я попробовал, и результат оказался 0,5, -5
nosense
1
"путь от источника к x к u даже не рассматривается"; Вы имели в виду источник от u до x?
slmatrix
1
@slmatrix спасибо, что уловили это, да, я имел в виду, что путь от источника до u к x, потому что x является соседом u.
Aditya P
23

Алгоритм Дейкстры предполагает, что пути могут становиться только «тяжелее», поэтому, если у вас есть путь от A до B с весом 3 и путь от A до C с весом 3, вы не можете добавить ребро и добраться из A в B через C с весом менее 3.

Это предположение делает алгоритм быстрее, чем алгоритмы, которые должны учитывать отрицательные веса.

zmbq
источник
8

Правильность алгоритма Дейкстры:

У нас есть 2 набора вершин на каждом шаге алгоритма. Набор A состоит из вершин, к которым мы вычислили кратчайшие пути. Набор B состоит из оставшихся вершин.

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

Индуктивный шаг : когда мы добавляем вершину V к множеству A и устанавливаем расстояние равным dist [V], мы должны доказать, что это расстояние является оптимальным. Если это не оптимально, то к вершине V должен существовать другой путь меньшей длины.

Предположим, что через некоторую вершину X проходит другой путь.

Теперь, поскольку dist [V] <= dist [X], следовательно, любой другой путь к V будет иметь длину как минимум dist [V], если только граф не имеет отрицательной длины ребер.

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

Nikunj Banka
источник
6

Попробуйте алгоритм Дейкстры на следующем графике, предполагая, что Aэто исходный узел, чтобы увидеть, что происходит:

график

ТБ-
источник
6
Извините, но я не получаю никаких сообщений об ошибках. Сначала A->Bбудет 1и A->Cбудет 100. Тогда B->Dбудет 2. Тогда C->Dбудет -4900. Значит, стоимость Dбудет -4900такая же, как у беллмана-форда. Как это неправильный ответ?
Анирбан Наг 'tintinmj'
9
@tintinmj Если у вас есть исходящее ребро от D, оно будет посещено до того, как расстояние D уменьшится, и, следовательно, не будет обновлено после его уменьшения. Тогда это обязательно приведет к ошибке. Если вы считаете D 2 как конечное расстояние уже после сканирования исходящих ребер, даже этот график приведет к ошибке.
Christian Schnorr
@ tb- Извините за вопрос после такого долгого времени, но я на правильном пути? Первый A->Bбудет 1и A->Cбудет 100. Затем Bисследуется и приступает B->Dк работе 2. Затем исследуется D, потому что в настоящее время у него кратчайший путь к источнику? Правильно ли я скажу, что если бы B->Dбыл 100, Cто сначала исследовали бы? Я понимаю все другие примеры, которые приводят люди, кроме вашего.
Pejman Poh
@PejmanPoh из моего понимания, если B-> D было 100, так как A-> C выше в HeapStructure, который будет использоваться, извлечение min сначала вернет A-> C, что означает, что следующий найденный кратчайший путь будет путем к C, после этого путь от C-> D с весом -5000 будет очевидным выбором, что приведет нас к выводу, что кратчайший путь будет от A-> C-> D, и я почти уверен, что это будет быть нормальным поведением. Так что иногда, когда у нас есть отрицательные циклы, мы все же можем получить правильное значение для кратчайшего пути, но определенно не всегда, это пример, когда мы этого не сделаем ..
Т.Димитров
1

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

Vineet
источник
0

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

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

Учти это:

A  <- 5 ->  B  <- (-1) ->  C <- 5 -> D

Каков оптимальный путь между A и D?

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

Dakkaron
источник
0

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

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

CodingLab
источник