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

Question

Можем ли мы использовать алгоритм Дейкстры с отрицательными весами?

STOP! Прежде чем вы думаете, "LOL NUB, вы можете просто бесконечно прыгать между двумя точками и получить бесконечно дешевый путь", яЯ больше думаю об односторонних путях.

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

Я думал об увеличении веса всех точек до тех пор, пока они не будут отрицательными, но я не уверен, будет ли эторабота.

Answer 1

Пока граф не содержит отрицательный цикл (направленный цикл, у которого граничные веса имеют отрицательную сумму), он будет иметь кратчайший путь между любыми двумя точками, но алгоритм Дейкстры не предназначен для их поиска. Самым известным алгоритмом нахождения кратчайших путей из одного источника в ориентированном графе с отрицательным весом ребер является алгоритм Беллмана-Форда . Однако это обходится дорого: Bellman-Ford требует времени O (| V | · | E |), в то время как 1004 * Дейкстры требует времени O (| E | + | V | log | V |), что асимптотически быстрее как для разреженных графов (где E - O (| V |)), так и для плотных графов (где E - O (| V | ^ 2)).

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

Увеличение всех весов на постоянное значение, чтобы они были неотрицательными, работать не будет. Чтобы увидеть это, рассмотрим график, на котором есть два пути от A до B, один из которых пересекает одно ребро длины 2, а другой - через ребра длины 1, 1 и -2. Второй путь короче, но если вы увеличиваете все веса ребер на 2, первый путь теперь имеет длину 4, а второй путь имеет длину 6, переворачивая самые короткие пути. Эта тактика будет работать, только если все возможные пути между двумя точками используют одинаковое количество ребер.

Answer 2

Если вы прочитаете доказательство оптимальности, одно из сделанных предположений состоит в том, что все веса неотрицательны. Итак, нет . Как рекомендует Барт, используйте Bellman-Ford, если на вашем графике нет отрицательных циклов.

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

Я рекомендую вам прочитать доказательство оптимальности - там вы увидите, что предположение о том, что добавление ребра к существующему пути может только увеличить (или не повлиять) стоимость пути, является критическим.

Answer 3

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

Способ, которым это работает, заключается в добавлении нового узла (скажем, Q), стоимость которого равна 0 для прохождения к каждому другому узлу в графе. Затем он запускает Беллмана-Форда на графике из точки Q, получая стоимость для каждого узла по отношению к Q, которую мы будем называть q [x], которая будет либо 0, либо отрицательным числом (так как использовался один из отрицательных путей ).

например. a -> -3 -> b, поэтому, если мы добавим узел Q, стоимость которого равна 0, для всех этих узлов, то q [a] = 0, q [b] = -3.

Затем мы перебалансируем ребра, используя формулу: weight + q [source] - q [destination], поэтому новый вес a-> b равен -3 + 0 - (-3) = 0. Мы делаем это для всех остальных ребер в графе, затем удалите Q и его исходящие ребра и вуаля! Теперь у нас есть ребалансированный граф без отрицательных ребер, к которому мы можем запустить dijkstra's!

Время работы: O (нм) [Беллман-форд] + n x O (m log n) [n Дейкстры] + O (n ^ 2) [вычисление веса] = O (нм log n) время

Дополнительная информация: http://joonki -jeong.blogspot.co.uk / 2013/01 / johnsons -gorith.html

Answer 4

Вы можете использовать Dijkstra's на отрицательном взвешенном графике, но сначала вы должны найти правильное смещение для каждой вершины.Это по сути то, что делает алгоритм Джонсона.Но это было бы излишним, так как Джонсон использует Bellman-Ford, чтобы найти смещение веса.Johnson's предназначен для всех кратчайших путей между парами вершин.

http://en.wikipedia.org/wiki/Johnson%27s_algorithm

Answer 5

Дерево выражений - это двоичное дерево, в котором все листья являются операндами (константами или переменными), а нествольные узлы являются двоичными операторами (+, -, /, *, ^).Реализуйте это дерево для моделирования полиномов с помощью основных методов дерева, включая следующие:

1. Функция, которая вычисляет первую производную полинома.
2. Оценить полином для заданного значенияиз х.

[20] Используйте следующие правила для производной: Производная (постоянная) = 0 Производная (x) = 1 Производная (P (x) + Q (y)) = Производная (P (x)) + Производная (Q (y)) Производная (P (x) - Q (y)) = Производная (P (x)) - Производная (Q (y)) Производная (P (x) * Q (y)) = P (x) * Производная (Q (y)) + Q (x) * Производная (P (x)) Производная (P (x) / Q (y)) = P (x) * Производная (Q(y)) - Q (x) * Производная (P (x)) Производная (P (x) ^ Q (y)) = Q (y) * (P (x) ^ (Q (y) - 1))* Производное (Q (y))

Answer 6

Да, вы можете сделать это, добавив один шаг в конце, т.е.

            If v ∈ Q, Then Decrease-Key(Q, v, v.d)
            Else Insert(Q, v) and S = S \ {v}.

Answer 7

На самом деле я думаю, что это сработает, чтобы изменить вес ребер.Не со смещением, а с фактором.Предположим, что вместо измерения расстояния вы измеряете время, требуемое от точки A до B.

вес = время = расстояние / скорость

Вы можете даже адаптировать скорость в зависимости от наклона для использованияодин, если ваша задача для настоящих гор и автомобиля / велосипеда.