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

Ответ 1

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

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

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

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

Dijkstra из A сначала разработает C и позже не найдет A->B->C

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

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

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

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

Ответ 2

Рассмотрим приведенный ниже график с источником как Vertex A. Сначала попробуйте запустить сам алгоритм Dijkstras.

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

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

Сначала мы извлекаем вершину из 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, когда вы идете .

Итак, для этого графика Dijkstra Algorithm ошибочно вычисляет расстояние от A до C.

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

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

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

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

Итак, я говорю, что при запуске этого алгоритма, если 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 являются соседями. B имеет один соседний C и C не имеет соседей. length (a, b) - длина края между вершинами a и b.

Ответ 3

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

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

Ответ 4

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

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

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

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

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

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

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

Ответ 5

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