Используется ли алгоритм Дейкстры, даже если имеется только один отрицательный вес?

Ответ 1

Нет. Алгоритм Дейкстры - жадный. Он предполагает, что весы пути строго возрастают.

Рассмотрим следующий график. S → A → E является оптимальным, но Dijkstra будет возвращать S → B.

Ответ 2

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

Надеюсь, это поможет!

Ответ 3

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

Ответ 4

Нет. Рассмотрим следующий простой контрпример с тремя узлами, S (старт), A и B.

w(S, A) = 1
w(S, B) = 2
w(B, A) = -2

Алгоритм сначала исправит расстояние для A (стоимость 1), но дешевле отправиться туда через B (стоимость 0).

Ответ 5

Поскольку алгоритм Дейкстры является жадным, он не будет работать с отрицательными весами. Для этой цели нужен другой алгоритм, такой как алгоритм Беллмана-Форда.

Но, если вы все еще хотите использовать Dijkstra Algo, есть известный способ. В этом методе вам нужно переназначить затраты, чтобы все стали положительными.

Вот он:

Предположим, что существует ребро от u до v, а стоимость края - стоимость (u, v).

u(d(u))------>v(d(v))

Определение:

new_cost(u,v) = cost(u,v) + d(u) - d(v)

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

d(v) < d(u) + cost(u,v)

Теперь мы можем применить алгоритм Дейкстра, как правило, только различие, являющееся стоимостью нового пути, которое будет (скажем, путь находится между s 'и t')

= original cost of the same path + d(s') - d(t')

Ответ 6

Вы не можете применить алгоритм Дейкстры непосредственно к графу с отрицательным краем, как правильно отметили некоторые другие ответы.

Существует способ перераспределить границы графа, если в исходном графе нет отрицательных циклов. Это тот же метод, который использовался в алгоритме Джонсона, где сначала вы запускали один экземпляр алгоритма Беллмана-Форда для получения весов h(v) для каждой вершины v. Затем вы изменяете каждый ребро w(u,v) на w(u,v) + h(u) − h(v), который гарантированно будет положительным, поэтому вы получите новый график с только положительными ребрами, на которых вы можете запустить алгоритм Дейкстры.

Раздел XV. из класса Coursera "Алгоритмы" объясняет это намного лучше, чем я.

Единственная проблема с применением этого метода для проблемы с одним самым коротким путём заключается в том, что при взвешивании с использованием Bellman-Ford требуется время O(mn), которое медленнее, чем Dijkstra O(m log(n)). Таким образом, вам лучше просто запустить Bellman-Ford для вашего первоначального графика.

Ответ 7

Нет, алгоритм Дейкстры, как известно, не работает с отрицательными весами. Если вам нужны отрицательные веса, используйте алгоритм Беллмана-Форда.

Ответ 8

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

Ответ 9

ПОЧЕМУ Dijkstra может сбить его с толку

потому что должен быть самый короткий путь: расстояние (s, vi) ≤ расстояние (s, vk)

Для примера у нас есть этот график:

A ---- > B со стоимостью 2 B --- > C со стоимостью минус 4 условие было False Теперь, потому что расстояние от A до B > расстояние B до C