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

Question

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

Answer 1

Что означает найти наименее дорогой путь от A до B, если каждый раз, когда вы путешествуете с C на D, вы получаете уплаченный?

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

Это не связано с алгоритмом, и все это связано с невозможностью ответить на такой вопрос.

Edit:

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

В таком случае алгоритм Дейкстры может по-прежнему не:

Рассмотрим два пути:

• оптимальный путь, стеллажи вверх стоимость 100, до пересечения конечного края, который имеет -25 вес, что дает в общей сложности 75, и
• неоптимальный путь, который не имеет отрицательно взвешенным края с общей стоимостью 90

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

Answer 2

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

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

Однако, пока вокруг графика нет направленных циклов, вы можете избежать использования Алгоритма Дейкстры без всякого взрыва на вас.

Все, что сказано, если у вас есть график с отрицательными весами, вы можете использовать алгоритм Belman-Ford. Однако из-за общности этого алгоритма он немного медленнее. Алгоритм Беллмана-Форда принимает O (V · E), где Dijkstra принимает O (E + VlogV) время

Answer 3

Я дам вам контрпример. Рассмотрим следующий граф

http://img853.imageshack.us/img853/7318/3fk8.png

Предположим, что вы начали в вершине A и вы хотите кратчайший путь к D.Алгоритм Дейкстры бы сделать следующие шаги:

1. Марк A как посещенные и добавить вершины B и C в очередь
2. Fetch из очереди вершины с минимальным расстоянием. Это B
3. Отметить B как посетил и добавить вершину D в очередь.
4. Извлечь из очереди. Это не вершина D.
5. Марк D как посещенные

Дейкстра говорит кратчайший путь от A к D имеет длину 2, но это явно не так.