Почему алгоритм кратчайшего пути Dijkstra на основе приоритетов не может работать для графика отрицательных весов? [Дубликат]

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

[/g16]

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

[/g17]

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

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

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

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

Итак, мы закончили с расстояниями как

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

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

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

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

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

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

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

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

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

Но это зависит от нашего предположения о положительной длине ребра, если длина (u, v) & lt 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.

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

[/g0]

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

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

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

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

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

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

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

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

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