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

Ответ 1

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

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

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

Ответ 2

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

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

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

Ответ 3

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

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

Ответ 4

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

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

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

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

Время работы: O (nm) [bellman-ford] + nx O (m log n) [n Dijkstra's] + O (n ^ 2) [вычисление веса] = O (nm log n) time

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

Ответ 5

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

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

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

Ответ 6

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

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

Ответ 7

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

• Функция, которая вычисляет первую производную от полинома.
• Вычислить полином для заданного значения x.

[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))