Будет ли алгоритм Дейкстры работать, если орграф имеет только один отрицательный вес и не содержит отрицательных весовых циклов?Действует ли алгоритм Дейкстры, даже если имеется только один отрицательный край веса?
Нет. Алгоритм Дейкстры является жадным. Он предполагает, что весы в пути строго возрастают.
Рассмотрите следующий график. S → → E является оптимальным, но Дейкстры вернется S → → B E.
Я думаю, что этот встречный пример ошибочен - '' 'вершина будет выскользена наконец, а затем алгоритм расслабит край' AE', и поэтому выбранный путь будет 'S-> A-> E', как и ожидалось , – Elimination
Как только S → B → E обнаружен, Dijkstra's не продолжает поиск. Вот что значит быть жадным. Он принимает первое решение, которое он находит, и не ищет дополнительных, лучших. Когда все веса неотрицательны, их не будет лучше. –
Неправильно (Насколько я могу судить): Я рассмотрел алгоритм, представленный в книге CLRS. ** Алгоритм останавливается, когда очередь приоритета пуста **. Поэтому, когда 'A' выскочит из p-очереди, мы расслабим край' A-> E', как я сказал выше. – Elimination
Не обязательно. В this earlier answer я привел пример графика без отрицательных циклов и одного отрицательного ребра, где алгоритм Дейкстры не дает правильного ответа. Поэтому алгоритм Дейкстры не всегда работает в этом случае.
Надеюсь, это поможет!
No. Dijkstra - жадный алгоритм. Когда он добавит край, он никогда не оглядывается назад.
Нет. Рассмотрим следующий простой контрпример с тремя узлами, S (начало), A и B.
w(S, A) = 1
w(S, B) = 2
w(B, A) = -2
алгоритм зафиксирует расстояние для A первого (стоимость 1), но дешевле ехать туда через B (стоимость 0).
Я думаю, что это неправильно; вершина 'B' выскочит из очереди приоритетов, а затем мы расслабим край' B-> A'. Обратите внимание, что алгоритм останавливается, когда p-очередь пуста! – Elimination
@Elimination Dijkstra генерирует остовное дерево. Самый короткий путь от S до A - 'S-> B-> A' (вес 0). Самый короткий путь от S до B - 'S-> A-> B' (вес -1). Эти пути не могут быть оба в остовном дереве, потому что это не будет дерево. –
Нет, Dijkstras Алгоритм хорошо известен, чтобы не работать с отрицательными весами. Если вам нужны отрицательные веса, используйте алгоритм Беллмана-Форда.
Поскольку алгоритм Дейкстры является жадным, он не будет работать с отрицательными весами. Для этой цели нужен другой алгоритм, такой как алгоритм Беллмана-Форда.
Но, если вы все еще хотите использовать Алго Дейкстры, есть известный способ. В этом методе вам нужно переназначить затраты, чтобы все стали положительными.
Вот он:.
Пусть имеется ребро от и до V А стоимость края является стоимость (и, 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')
Можете ли вы описать, где вы получили эту информацию (перепроектируя затраты) на научную бумагу? автор? Потому что я слышал от ученого, специализировавшегося на Dijkstras Algo, что многие пытались использовать Dijkstra с отрицательными весами, но ни один из них не преуспел. – AlexWien
Что такое d (u)? ..... – AlexWien
Я не использую алгоритм Дейкстры на отрицательных весах. Это просто невозможно. Я просто использую математические манипуляции для изменения самих затрат.Если вы внимательно наблюдаете, новые и старые издержки будут варьироваться в зависимости от константы. – Ranveer
Вы не можете применить алгоритм Дейкстры непосредственно к графику с отрицательным ребром, как некоторые из других ответов правильно отметили.
Существует способ переопределить края графа, учитывая, что в исходном графе нет отрицательных циклов.Это тот же метод, который используется в Johnson's algorithm, где сначала вы запускаете один экземпляр алгоритма Беллмана-Форда для получения весов h(v) для каждой вершины v. Затем вы изменяете каждое ребро w(u,v) на w(u,v) + h(u) − h(v), которое гарантированно будет положительным, и вы получите новый график с положительными ребрами, на котором вы можете запустить алгоритм Дейкстры.
Раздел XV. от Coursera Algorithms class объясняет это намного лучше меня.
Единственная проблема, связанная с применением этой техники для проблемы с самым коротким единственным источником, заключается в том, что перевес с Bellman-Ford занимает O(mn) время, которое медленнее, чем у Dijkstra. Таким образом, вам лучше просто запустить Bellman-Ford для вашего первоначального графика.
ПОЧЕМУ Дейкстры может потерпеть неудачу Это просто
потому что Кратчайший путь должен быть: расстояние (s, VI) ≤ расстояние (s, VK)
Для Exemple у нас есть этот график:
A ----> B со стоимостью 2 B ---> C со стоимостью минус 4 условие было ложным Теперь, потому что расстояние от A до B> расстояние B до C
Алгоритм Дейкстры будет работать с одним отрицательным ребром как долго когда вы начинаете с узла, у которого этот отрицательный край является n исходящий край.
. Начав с наименьшего значащего края графика, вы больше не можете уменьшить общую стоимость, рассматривая другие весы ребер (как работает алгоритм Дейкстры)
Возможный дубликат [Отрицательные веса с использованием алгоритма Дейкстры] (http: //stackoverflow.com/questions/6799172/negative-weights-using-dijkstras-algorithm) –
@ JerryCoffin- Я не думаю, что это дубликат. Этот вопрос задает вопрос о алгоритме Дейкстры с очень специфическим ограниченным набором отрицательных ребер, в то время как исходный вопрос заключается в том, почему алгоритм Дейкстры не работает на общих графах с отрицательными ребрами. – templatetypedef