Можете ли вы использовать алгоритм Дейкстры, если есть отрицательный вес, если нет циклов? - PullRequest
Новая
       26

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

2 голосов
/ 26 сентября 2011

Обновление : Я действительно испортил исходный вопрос. Мое первоначальное название было «Почему мы сначала делаем топологическую сортировку для задач ациклического взвешенного орграфа по кратчайшему пути?» но мой вопрос содержал информацию об алгоритме Дейкстры. Надеюсь, с тех пор, как я сменил название, вопрос обновляется таким образом, чтобы он пригодился кому-то еще. Ответ на обновленный заголовок вопроса: « да ».

Оригинальный вопрос :

Зачем мне сначала делать топологическую сортировку? (см. Код здесь) Разве я не могу просто использовать алгоритм Дейкстры, показанный ниже, и вообще избежать топологической сортировки (немного беспорядочно в синтаксисе, но вы поняли идею) 

MinIndexedPriorityQueue waitingEdges = new MinIndexedPriorityQueue
Graph g //some weighted directed graph
double[] distTo = new double[g.vertexCount]
Edge[] edgeTo = new Edge[g.vertexCount]
int source = //init to some value

void minPathInit()
    init distTo to double.MAX_VALUE
    //init first node
    distTo [source] = 0
    visit(source)
    while waitingEdges.count>0
        int vertex = waitingEdges.dequeue()
        relax(vertex )

void relax(v) //note that visit has been renamed to relax
    for each edge in graph.getEdgesFrom(v)
        int to= edge.to
        if edge.weight + distTo [edge.from]<  distTo [to]
            distTo[to] = edge.weight + distTo [edge.from]
            edgeTo[to] = edge
            if waitingEdges.contains(to)
                waitingEdges.change(to,  distTo[to] )
            else
                waitingEdges.enqueue(to,  distTo[to] )


//after everything is initialized
getPathTo(v)
    if not hasBeenVisited[v]
        return null
    Stack path = new Stack
    while edgeTo[v] != source
        path.push(edgeTo[v])
        v = edgeTo[v].from
    return path

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

Обновление: Хорошо, я вижу, что я задал этот вопрос, поэтому я попытаюсь исправить его с помощью обновления. Спасибо, что нашли время указать мне на это. Я ошибочно думал, что AcyclicSP становится алгоритмом Дейкстры при удалении топологической сортировки, что не так.

Однако мой вопрос об алгоритме Дейкстры (с использованием версии, показанной выше) остается. Почему его нельзя использовать, даже если есть отрицательный вес, если нет циклов? Здесь есть java-версия алгоритма Дейкстры . Мой очень похож на это (поскольку я узнал об этом из книги этого парня), но его пример, вероятно, легче читать некоторым из вас.

Ответы [ 3 ]

3 голосов
/ 26 сентября 2011

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

2 голосов
/ 26 сентября 2011

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

Алгоритм Дейкстры не поддерживает отрицательную стоимость пути, но обрабатывает циклы цикла.Это делается путем остановки, когда он обнаруживает, что существует более короткий путь к узлу.Цикл пути не будет короче и остановится (при условии, что стоимость не отрицательна)

1 голос
/ 22 ноября 2012

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

Используйте Bellman-Ford Algo, если у вас нег. Масса

...