Dijkstra Rechner

Pseudocode

Dijkstra ist ein gieriger Algorithmus, dessen Korrektheit auf einer einzigen Behauptung ruht: Der nächstgelegene noch offene Knoten kann später nicht mehr verbessert werden. Eine Prioritätswarteschlange liefert diesen Knoten in O(log V).

Dijkstra(graph, quelle):
    für jeden Knoten v: dist[v] = unendlich
    dist[quelle] = 0
    pq = Prioritätswarteschlange mit (0, quelle)

    solange pq nicht leer ist:
        (d, u) = pq.entnimmMinimum()
        wenn d > dist[u]: weiter      // veralteter Eintrag
        für jede Kante (u, v, w):
            wenn dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                vorgänger[v] = u
                pq.einfügen((dist[v], v))

Die Prüfung auf veraltete Einträge ist wichtig. Statt den Schlüssel im Heap zu verringern, was die meisten Standardbibliotheken nicht unterstützen, fügt man üblicherweise einen doppelten Eintrag ein und ignoriert jeden, dessen gespeicherte Distanz nicht mehr passt. Das heißt verzögertes Löschen und ist der Grund, warum die Warteschlange bis zu E statt V Einträge halten kann.

Durchgerechnetes Beispiel, Schritt für Schritt

Führe Dijkstra von A aus auf einem gewichteten Graphen, in dem sich die gierige Wahl auszahlt, und beobachte, wie die Menge der endgültigen Knoten wächst.

Beispielgraph: Ungerichtete Kanten A-B (4), A-C (2), C-B (1), B-D (5) und C-D (8).

1. Initialisieren. dist = A 0, B unendlich, C unendlich, D unendlich. Die Warteschlange enthält (0, A).
2. A bei 0 festlegen. Relaxiere A-B zu dist[B] = 4 und A-C zu dist[C] = 2. Die Warteschlange enthält (2, C) und (4, B).
3. C bei 2 festlegen. C ist näher als B und kommt daher zuerst heraus. Relaxiere C-B: 2 + 1 = 3, besser als die eingetragene 4, also dist[B] = 3 und ein neuer Eintrag (3, B) wird eingefügt. Relaxiere C-D: 2 + 8 = 10, also dist[D] = 10.
4. B bei 3 festlegen. Der Eintrag (3, B) erscheint vor dem veralteten (4, B). Relaxiere B-D: 3 + 5 = 8, besser als 10, also dist[D] = 8.
5. Veralteten Eintrag überspringen. Nun taucht der alte Eintrag (4, B) auf. Da 4 größer ist als dist[B] von 3, wird er verworfen, ohne B erneut zu bearbeiten. Hier wirkt das verzögerte Löschen.
6. D bei 8 festlegen. Es bleibt nichts mehr zu verbessern. Der Algorithmus endet.

Die Enddistanzen sind A 0, C 2, B 3, D 8, und der kürzeste Weg zu D führt über A, C, B und D. Beachte, dass die direkte Kante A-B mit Gewicht 4 nie genutzt wird: der Weg über C kostet 3. Beachte außerdem, dass die Knoten in der Distanzreihenfolge 0, 2, 3, 8 endgültig werden, was genau die Eigenschaft ist, auf der das gierige Argument beruht.

Komplexität und woher sie kommt

Zeit: O((V + E) log V) · Speicher: O(V)

Mit einem Binärheap wird jeder der V Knoten einmal zu O(log V) entnommen, und jede der E Kanten kann eine Einfügung zu O(log V) auslösen, was O((V + E) log V) ergibt. Mit verzögertem Löschen enthält der Heap bis zu E Einträge, die Entnahme kostet also O(log E), doch da E höchstens V hoch 2 ist, liegt log E bei höchstens 2 log V und die Schranke bleibt gleich. Ein Fibonacci-Heap verbessert die theoretische Schranke auf O(E + V log V), weil das Verringern des Schlüssels amortisiert O(1) wird, allerdings sind die Konstanten so ungünstig, dass Binärheaps in der Praxis meist gewinnen. Bei einem dichten Graphen liefert ein einfacher Feldsuchlauf nach dem Minimum O(V hoch 2), was den Heap schlägt, sobald E sich V hoch 2 nähert.

Wann Dijkstra-Algorithmus passt und wann nicht

Dijkstra ist die Voreinstellung für gewichtete kürzeste Wege. Was ihn ersetzt, hängt davon ab, welche seiner Annahmen dein Graph verletzt.

Häufige Fehler

• Einsatz bei negativen Kantengewichten. Das ist der klassische Fehlgebrauch. Dijkstra legt einen Knoten endgültig fest, sobald er die Warteschlange verlässt; eine später gefundene negative Kante hätte ihn verbessert, doch er wird nie wieder betrachtet. Das Ergebnis ist stillschweigend falsch statt ein Fehler, was den Bug schwer auffindbar macht. Nimm stattdessen Bellman-Ford.
• Die Prüfung auf veraltete Einträge weglassen. Ohne die Absicherung `wenn d > dist[u]: weiter` wird ein Knoten je Warteschlangeneintrag erneut bearbeitet. Der Algorithmus terminiert weiterhin und liefert korrekte Antworten, relaxiert aber unnötig Kanten und kann bei vielen Verbesserungen stark einbrechen.
• Beim ersten Anblick des Ziels abbrechen. Das Ziel während einer Relaxation zu erreichen bedeutet nicht, dass seine Distanz endgültig ist. Endgültig ist sie erst, wenn das Ziel aus der Warteschlange entnommen wird. Ein Abbruch beim Entdecken liefert falsche Antworten, ein Abbruch beim Entnehmen ist korrekt und eine echte Optimierung.
• Kanten mit Gewicht null für problematisch halten. Nullgewichte sind unproblematisch. Nur strikt negative Gewichte brechen das Argument, denn der gierige Beweis braucht entlang eines Weges nicht fallende Distanzen, und null erhält diese Eigenschaft.
• Den ganzen Graphen je Anfrage neu aufbauen. Ein Dijkstra-Lauf liefert die Distanzen von der Quelle zu allen Knoten, nicht nur zu einem. Brauchst du viele Quellen, ist das ein anderes Problem: prüfe Floyd-Warshall oder Johnson, statt Dijkstra gedankenlos V-mal auszuführen.

Häufig gestellte Fragen

Wofür wird der Dijkstra-Algorithmus verwendet?

Er findet den kürzesten Weg von einer Quelle zu allen anderen Knoten in einem Graphen mit nichtnegativen Kantengewichten. Er treibt GPS- und Nahverkehrsrouting, Routingprotokolle wie OSPF und IS-IS, die Analyse von Netzwerklatenzen sowie Wegfindung in Spielen, wenn keine Heuristik verfügbar ist.

Wie ist die Zeitkomplexität des Dijkstra-Algorithmus?

O((V + E) log V) mit einem Binärheap, der Standardimplementierung. Ein Fibonacci-Heap senkt sie theoretisch auf O(E + V log V), doch die Konstanten machen Binärheaps meist schneller. Bei dichten Graphen liefert ein einfacher Feldsuchlauf O(V hoch 2), was den Heap schlagen kann, sobald E sich V hoch 2 nähert.

Warum versagt der Dijkstra-Algorithmus bei negativen Gewichten?

Weil er jeden Knoten endgültig festlegt, sobald dieser die kleinste vorläufige Distanz in der Warteschlange hat, in der Annahme, kein späterer Weg könne kürzer sein. Eine negative Kante verletzt diese Annahme: ein danach gefundener Weg kann eine bereits festgelegte Distanz verringern. Da Dijkstra festgelegte Knoten nie erneut betrachtet, liefert er ohne jede Fehlermeldung ein falsches Ergebnis.

Was ist der Unterschied zwischen Dijkstra und A*?

A* ist Dijkstra plus eine heuristische Schätzung der Restdistanz zu einem bestimmten Ziel. Dijkstra expandiert Knoten nach Distanz von der Quelle und findet Wege zu allem; A* expandiert nach geschätzten Gesamtkosten und strebt ein Ziel an, wobei er weit weniger Knoten erkundet. Mit einer Nullheuristik ist A* exakt Dijkstra.

Funktioniert der Dijkstra-Algorithmus auf ungerichteten Graphen?

Ja. Eine ungerichtete Kante besteht schlicht aus zwei gerichteten Kanten gleichen Gewichts, der Algorithmus gilt also unverändert. Die einzige echte Voraussetzung ist, dass kein Gewicht negativ ist.