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

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

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

5 87
algorithm shortest-path dijkstra

5 ответов:

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

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

       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

EDIT немного более глубокое объяснение:

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

Беллмана-Форда предлагает рекурсивное решение (DP) для этого.
120

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

enter image description here

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

Dijkstra’s algorithm

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

initialization

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

first iteration

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

second iteration

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

3rd?

поэтому мы в конечном итоге с расстояния

no change guys

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

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

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

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

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

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

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

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

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

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

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

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

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

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

26

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

16

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

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

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

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

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

теперь, поскольку dist[V]

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

5

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

Graph

3