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

Question

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

Answer 1

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

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

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

Редактировать

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

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

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

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

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

Answer 2

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

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

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

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

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

Answer 3

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

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

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