Warum verwendet der Dijkstra-Algorithmus den Abnahmeschlüssel?

Der Algorithmus von Dijkstra wurde mir wie folgt beigebracht

while pqueue is not empty:
    distance, node = pqueue.delete_min()
    if node has been visited:
        continue
    else:
        mark node as visited
    if node == target:
        break
    for each neighbor of node:
         pqueue.insert(distance + distance_to_neighbor, neighbor)

Aber ich habe etwas über den Algorithmus gelesen und viele Versionen, die ich sehe, verwenden die Abnahme-Taste im Gegensatz zum Einfügen.

Warum ist das so und was sind die Unterschiede zwischen den beiden Ansätzen?

Der Grund für die Verwendung des Verkleinerungsschlüssels anstelle des erneuten Einfügens von Knoten besteht darin, die Anzahl der Knoten in der Prioritätswarteschlange klein zu halten, wodurch die Gesamtzahl der Warteschlangen der Prioritätswarteschlange klein und die Kosten für jeden Prioritätswarteschlangensaldo niedrig gehalten werden.

In einer Implementierung des Dijkstra-Algorithmus, der Knoten mit ihren neuen Prioritäten wieder in die Prioritätswarteschlange einfügt, wird der Prioritätswarteschlange für jede der m Kanten im Diagramm ein Knoten hinzugefügt. Dies bedeutet, dass sich in der Prioritätswarteschlange M Enqueue-Operationen und M Dequeue-Operationen befinden, was eine Gesamtlaufzeit von O (m T _e + m T _d ) ergibt , wobei T _e die Zeit ist, die zum Einreihen in die Prioritätswarteschlange erforderlich ist, und T _d ist Die Zeit, die erforderlich ist, um die Warteschlange aus der Prioritätswarteschlange zu entfernen.

In einer Implementierung des Dijkstra-Algorithmus, der den Verkleinerungsschlüssel unterstützt, beginnt die Prioritätswarteschlange, die die Knoten enthält, mit n Knoten darin und entfernt bei jedem Schritt des Algorithmus einen Knoten. Dies bedeutet, dass die Gesamtzahl der Heap-Warteschlangen n beträgt. Auf jedem Knoten wird möglicherweise einmal für jede Kante, die in ihn führt, ein Verkleinerungsschlüssel aufgerufen, sodass die Gesamtzahl der durchgeführten Verkleinerungsschlüssel höchstens m beträgt. Daraus ergibt sich eine Laufzeit von (n T _e + n T _d + T m _k ), wobei T _k die Zeit , um Anruf Abnahme-Schlüssel erforderlich ist.

Wie wirkt sich das auf die Laufzeit aus? Das hängt davon ab, welche Prioritätswarteschlange Sie verwenden. Hier ist eine kurze Tabelle, die verschiedene Prioritätswarteschlangen und die Gesamtlaufzeiten der verschiedenen Dijkstra-Algorithmusimplementierungen zeigt:

Queue          |  T_e   |  T_d   |  T_k   | w/o Dec-Key |   w/Dec-Key
---------------+--------+--------+--------+-------------+---------------
Binary Heap    |O(log N)|O(log N)|O(log N)| O(M log N)  |   O(M log N)
Binomial Heap  |O(log N)|O(log N)|O(log N)| O(M log N)  |   O(M log N)
Fibonacci Heap |  O(1)  |O(log N)|  O(1)  | O(M log N)  | O(M + N log N)

Wie Sie sehen können, gibt es bei den meisten Arten von Prioritätswarteschlangen keinen Unterschied in der asymptotischen Laufzeit, und die Version mit abnehmendem Schlüssel wird wahrscheinlich nicht viel besser abschneiden. Wenn Sie jedoch eine Fibonacci-Heap- Implementierung der Prioritätswarteschlange verwenden, ist der Dijkstra-Algorithmus bei Verwendung des Abnahmeschlüssels tatsächlich asymptotisch effizienter.

Kurz gesagt, die Verwendung der Abnahmetaste und einer Warteschlange mit guter Priorität kann die asymptotische Laufzeit von Dijkstra über das Mögliche hinaus verringern, wenn Sie weiterhin Warteschlangen und Warteschlangen ausführen.

Abgesehen von diesem Punkt verwenden einige fortgeschrittenere Algorithmen, wie beispielsweise Gabows Shortest Paths-Algorithmus, den Dijkstra-Algorithmus als Unterprogramm und stützen sich stark auf die Implementierung des Abnahmeschlüssels. Sie nutzen die Tatsache, dass Sie, wenn Sie den Bereich der gültigen Entfernungen im Voraus kennen, basierend auf dieser Tatsache eine supereffiziente Prioritätswarteschlange erstellen können.

Hoffe das hilft!

Im Jahr 2007 gab es ein Papier, in dem die Unterschiede in der Ausführungszeit zwischen der Verwendung der Version mit verringertem Schlüssel und der Version mit Einfügung untersucht wurden. Siehe http://www.cs.utexas.edu/users/shaikat/papers/TR-07-54.pdf

Ihre grundlegende Schlussfolgerung war, für die meisten Diagramme nicht den Abnahmeschlüssel zu verwenden. Insbesondere bei spärlichen Diagrammen ist der Schlüssel zum Verringern der Schlüssel erheblich schneller als die Version zum Verringern des Schlüssels. Weitere Informationen finden Sie im Papier.

Es gibt zwei Möglichkeiten, Dijkstra zu implementieren: Eine verwendet einen Heap, der den Abnahmeschlüssel unterstützt, und eine andere einen Heap, der dies nicht unterstützt.

Sie sind beide im Allgemeinen gültig, wobei letzteres normalerweise bevorzugt wird. Im Folgenden werde ich mit 'm' die Anzahl der Kanten und mit 'n' die Anzahl der Eckpunkte unseres Diagramms bezeichnen:

Wenn Sie die bestmögliche Komplexität im ungünstigsten Fall wünschen, würden Sie sich für einen Fibonacci-Heap entscheiden, der die Abnahme-Taste unterstützt: Sie erhalten ein schönes O (m + nlogn).

Wenn Sie sich für den Durchschnittsfall interessieren, können Sie auch einen Binärheap verwenden: Sie erhalten O (m + nlog (m / n) logn). Der Beweis ist hier , Seiten 99/100. Wenn der Graph dicht ist (m >> n), tendieren sowohl dieser als auch der vorherige zu O (m).

Wenn Sie wissen möchten, was passiert, wenn Sie sie in realen Diagrammen ausführen, können Sie dieses Dokument überprüfen , wie Mark Meketon in seiner Antwort vorgeschlagen hat.

Die Versuchsergebnisse zeigen, dass ein "einfacherer" Haufen in den meisten Fällen die besten Ergebnisse liefert.

Unter den Implementierungen, die einen Abnahmeschlüssel verwenden, ist Dijkstra bei Verwendung eines einfachen Binärheaps oder eines Pairing-Heaps besser als bei Verwendung eines Fibonacci-Heaps. Dies liegt daran, dass Fibonacci-Haufen größere konstante Faktoren beinhalten und die tatsächliche Anzahl von Operationen mit abnehmenden Schlüsseln tendenziell viel kleiner ist als im schlimmsten Fall vorhergesagt.

Aus ähnlichen Gründen weist ein Heap, der keine Operation zum Verringern der Taste unterstützen muss, noch weniger konstante Faktoren auf und bietet tatsächlich die beste Leistung. Besonders wenn der Graph spärlich ist.