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

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

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

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

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

       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) для этого.

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

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

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

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

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

Наконец, мы извлекаем B, после чего . Обратите внимание, что 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 , путь будет даже не рассматриваются как возможный короткий путь от источника к 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

Учти это:

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

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

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

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

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