Was ist Dijkstra-Algorithmus?

Algorithmus, der in einem Graphen mit Kantengewichten größer oder gleich 0 die kürzesten Wege von einem Startknoten zu allen Knoten findet. Er legt wiederholt den nächstgelegenen Knoten, dessen Entfernung noch nicht feststeht, endgültig fest und aktualisiert die Entfernungen seiner Nachbarn. Bei negativen Kantengewichten arbeitet er nicht korrekt.

Japanische Bezeichnung: ダイクストラ法

„Dijkstra-Algorithmus“ kommt in 3 Übungsfragen aus 1 Themen vor, z. B. Datenstrukturen und Algorithmen.

Fachgebiet: Datenstrukturen und Algorithmen

Ablauf

Die Entfernung des Startknotens wird auf 0 und die aller anderen Knoten auf unendlich gesetzt, und kein Knoten gilt als festgelegt. Man wählt den nicht festgelegten Knoten mit der kleinsten Entfernung, legt ihn fest und aktualisiert für jede von ihm ausgehende Kante die Entfernung des Knotens am anderen Ende, wenn „festgelegte Entfernung + Kantengewicht“ kleiner als dessen aktuelle Entfernung ist (Relaxation). Das wird wiederholt, bis alle Knoten festgelegt sind. Wird bei jeder Aktualisierung der vorherige Knoten notiert, lässt sich der kürzeste Weg selbst anschließend zurückverfolgen.

Komplexität und Prioritätswarteschlangen

Jedes Mal alle Knoten nach dem Minimum zu durchsuchen, kostet bei V Knoten O(V²). Mit einer auf einem binären Heap beruhenden Prioritätswarteschlange sinkt das auf O((V + E) log V), wobei E die Zahl der Kanten ist; bei dünn besetzten Graphen wie Straßennetzen ist das deutlich schneller. Der Graph wird üblicherweise als Adjazenzlisten gespeichert. Navigationssysteme im Auto kombinieren ihn mit der A*-Suche, die eine Schätzung der Restentfernung addiert, um die Suche auf das Ziel auszurichten, und mit Beschleunigungsverfahren, die vorab berechnete Informationen nutzen.

Negative Gewichte und andere Algorithmen

Der Dijkstra-Algorithmus legt Knoten unter der Annahme fest, dass ein Umweg über andere Knoten eine Entfernung nur vergrößern, nie verkleinern kann. Mit negativen Kanten kann eine festgelegte Entfernung später kürzer werden, sodass korrekte Antworten nicht garantiert sind. Bei negativen Gewichten verwendet man den Bellman-Ford-Algorithmus, der jede Kante V−1-mal relaxiert und auch negative Zyklen erkennen kann. Für kürzeste Wege zwischen allen Knotenpaaren wird auch der auf dynamischer Programmierung beruhende Floyd-Warshall-Algorithmus (O(V³)) eingesetzt. Beim Routing in Netzwerken berechnen Link-State-Protokolle wie OSPF die Routen in jedem Router mit dem Dijkstra-Algorithmus.

Jetzt üben: Fragen zu Dijkstra-Algorithmus

In einem ungerichteten Graphen haben die Kanten die Gewichte (Entfernungen) S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3 und A−T: 6. Welcher kürzeste Weg von S nach T und welche Länge ergeben sich mit dem Dijkstra-Algorithmus?

AS→A→C→T, Länge 8
BS→B→A→C→T, Länge 7
CS→B→C→T, Länge 9

Antwort und Erläuterung anzeigen

Antwort: B. S→B→A→C→T, Länge 7

Der Dijkstra-Algorithmus legt wiederholt den nächstgelegenen Knoten, dessen Entfernung noch nicht feststeht, endgültig fest und aktualisiert die Entfernungen seiner Nachbarn. Ausgehend von S (0) wird B mit 1 festgelegt; über B erhält A die Entfernung 1 + 2 = 3, kürzer als die direkten 4. Mit der Festlegung von A (3) erhalten C den Wert 3 + 1 = 4 und T den Wert 3 + 6 = 9, und die Festlegung von C (4) aktualisiert T auf 4 + 3 = 7. Der kürzeste Weg ist daher S→B→A→C→T mit der Länge 7. S→A→C→T (8) ist länger, weil er S−A direkt nimmt, und S→B→C→T (9) ist länger, weil B−C das große Gewicht 5 hat.

Welche Bedingung an den Graphen ist erforderlich, damit der Dijkstra-Algorithmus korrekte kürzeste Wege findet?

ADer Graph enthält keine Zyklen (Wege, die zum selben Knoten zurückführen)
BDie Kanten sind ungerichtet
CAlle Kantengewichte sind größer oder gleich 0

Antwort und Erläuterung anzeigen

Antwort: C. Alle Kantengewichte sind größer oder gleich 0

Der Dijkstra-Algorithmus legt unter den noch nicht festgelegten Knoten denjenigen mit der kleinsten Entfernung endgültig fest. Das beruht auf der Annahme, dass ein Umweg über andere Knoten eine Entfernung nur vergrößern, nie verkleinern kann. Gibt es eine Kante mit negativem Gewicht, kann eine Entfernung später über einen anderen Weg kürzer werden; in einem gerichteten Graphen mit S→A 2, S→B 3 und B→A −2 wird A zum Beispiel mit 2 festgelegt, bevor der Weg S→B→A mit der Länge 1 gefunden wird. Bei negativen Gewichten verwendet man den Bellman-Ford-Algorithmus oder ähnliche Verfahren. Mit Zyklen und mit gerichteten Kanten funktioniert der Dijkstra-Algorithmus, solange alle Gewichte größer oder gleich 0 sind.

Häufige Fragen

Wie hängt der Dijkstra-Algorithmus mit der Breitensuche zusammen?

Haben alle Kanten das Gewicht 1, legt der Dijkstra-Algorithmus die Knoten in derselben Reihenfolge fest wie die Breitensuche. Er lässt sich als Verallgemeinerung für unterschiedliche Gewichte verstehen, die die Warteschlange durch eine Prioritätswarteschlange ersetzt, die die kleinste Entfernung zuerst liefert.

Lässt sich der Dijkstra-Algorithmus auf gerichtete Graphen anwenden?

Ja. Solange die Gewichte größer oder gleich 0 sind, findet er korrekte kürzeste Wege in gerichteten und ungerichteten Graphen, auch in Graphen mit Zyklen.

„Dijkstra-Algorithmus“ in den Erläuterungen

Der Dijkstra-Algorithmus legt wiederholt den nächstgelegenen Knoten, dessen Entfernung noch nicht feststeht, endgültig fest und aktualisiert die Entfernungen seiner Nachbarn.
In einem ungerichteten Graphen haben die Kanten die Gewicht…
Der Dijkstra-Algorithmus legt unter den noch nicht festgelegten Knoten denjenigen mit der kleinsten Entfernung endgültig fest.
Welche Bedingung an den Graphen ist erforderlich, damit der…
Für Verfahren, die nacheinander die von jedem Knoten ausgehenden Kanten verfolgen, etwa die Breitensuche und den Dijkstra-Algorithmus, sind Adjazenzlisten effizienter.
Wie lässt sich ein dünn besetzter Graph, also einer mit wen…