Могу ли я использовать алгоритм Дейкстры на DAG с отрицательно взвешенными ребрами?

Question

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

Но что, если ориентированный граф не содержит цикл, то есть ориентированный ациклический граф(DAG)?Я думаю, что алгоритм Дейкстры можно использовать даже с отрицательно взвешенными ребрами, чтобы найти путь минимальной стоимости.

Answer 1

Как правило, алгоритм Дейкстры нельзя использовать для построения графиков с отрицательными длинами ребер.Однако может быть особый случай.Если все отрицательные ребра в графе связаны с начальной точкой (также работает для пункта назначения, если вы переворачиваете начальную точку и пункт назначения в неориентированном графике).Алгоритм Дейкстры также предложит кратчайший путь.

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

В следующем примере, если вы начнете с s до t, используя алгоритм Дейкстры, это не будет работать, потому чтоКрай (v, t) уменьшает длину пути.

Пример

Однако, если мы начнем с t до s, используя алгоритм Дейкстры, он выбереткрай (v, t) вместо (s, t) и позже он выберет (s, v).Это будет работать, потому что только ребра, падающие на начальный узел, являются отрицательными, не повредит глобальные кратчайшие расстояния.На более поздней итерации будут выбраны только неотрицательные ребра, и добавление большего числа ребер обязательно увеличит длину.

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

Answer 2

Нет, его нельзя использовать при наличии отрицательных весов.Причина в том, что это жадный алгоритм.Как только он выбрал узел минимального расстояния, он не пересматривает этот выбор.Отрицательные веса позволят, чтобы какой-то другой узел позже в алгоритме стал ниже.

Вот простой пример счетчика:

start  -- 1 ----------> end
    |                    ^
    \ -- 2 --> x -- -3 --/

В этом случае алгоритм дает вам прямой путь веса 1вместо более короткого пути через узел x с весом -1.