Dijkstra-Algorithmus einfach erklärt

Stell dir ein Straßennetz vor: Orte sind Knoten, Straßen sind Kanten und die Fahrzeit jeder Straße ist ihr Kantengewicht. Gesucht ist nicht unbedingt die Route mit den wenigsten Straßen, sondern der Weg mit der kleinsten Summe aller Gewichte.

Dijkstra passt, wenn du kürzeste Wege von einem Startknoten zu einem Ziel oder zu allen erreichbaren Knoten suchst und kein Gewicht negativ ist. Ein nicht erreichbarer Knoten behält die Distanz unendlich, kurz $\infty$.

Die Breitensuche wählt dagegen nach der Anzahl der durchlaufenen Kanten aus. Sie genügt für ungewichtete Graphen oder für Graphen, in denen alle Kanten dasselbe Gewicht haben. Bei unterschiedlichen Gewichten kann ein Weg mit mehr Kanten trotzdem günstiger sein.

Für jeden Knoten speicherst du zwei Angaben:

• Distanz: die bisher kleinste bekannte Summe vom Start;
• Vorgänger: den Knoten direkt davor auf diesem bisher besten Weg.

Offene Knoten können noch verbessert werden. Wird der offene Knoten mit der kleinsten Distanz ausgewählt, gilt seine Distanz als endgültig.

Initialisieren

1. Setze die Distanz des Startknotens auf 0.
2. Setze alle anderen Distanzen auf $\infty$ oder behandle die Knoten zunächst als unentdeckt.
3. Setze alle Vorgänger auf „unbekannt“.
4. Halte die offenen Knoten so bereit, dass du den kleinsten Distanzwert findest.

Auswählen und relaxieren

Wähle den offenen Knoten u mit der kleinsten vorläufigen Distanz. Für jeden noch nicht endgültigen Nachbarn v berechnest du:

$$\text{Alternative}=\text{Distanz}[u]+\text{Gewicht}(u,v)$$

Ist die Alternative kleiner als die gespeicherte Distanz von v, ersetzt du Distanz und Vorgänger:

$$\text{Distanz}[v]=\text{Alternative},\qquad \text{Vorgänger}[v]=u$$

Diese Prüfung heißt Relaxierung. Ist die Alternative gleich groß oder größer, bleibt der Eintrag unverändert. Danach markierst du u als endgültig und wählst den nächsten kleinsten offenen Knoten.

Gesucht ist der kürzeste Weg vom Start D zum Ziel H. Der Graph ist ungerichtet; jede Kante kann also in beide Richtungen benutzt werden.

Vom Start bis zum Ziel

Start `D`: D hat Distanz 0. Die Nachbarn erhalten:

• E: $0+1=1$, Vorgänger D;
• C: $0+3=3$, Vorgänger D;
• F: $0+4=4$, Vorgänger D.

Knoten `E` mit Distanz `1`:

• A: $1+3=4$, Vorgänger E;
• B: $1+5=6$, Vorgänger E;
• zu F ergäbe sich $1+6=7$. Das ist schlechter als der gespeicherte Wert 4; F bleibt unverändert.

Knoten `C` mit Distanz `3`:

• zu A ergäbe sich $3+2=5$, also keine Verbesserung gegenüber 4;
• G: $3+2=5$, Vorgänger C.

Nun haben A und F beide Distanz 4. Bei einem Gleichstand darfst du einen der beiden wählen. Hier wird zuerst F bearbeitet.

Knoten `F` mit Distanz `4`: H wird mit $4+7=11$ und Vorgänger F erstmals entdeckt. Abbrechen wäre falsch, denn offene Knoten mit kleineren Distanzen können noch einen günstigeren Weg zu H eröffnen.

Knoten `A` mit Distanz `4`: Es entsteht keine Verbesserung.

Knoten `G` mit Distanz `5`: Der Weg zu H kostet $5+4=9$. Weil 9 kleiner als 11 ist, änderst du die Distanz von H auf 9 und den Vorgänger auf G.

Knoten `B` mit Distanz `6`: I wird mit $6+15=21$ und Vorgänger B entdeckt. Danach ist H mit Distanz 9 der kleinste offene Knoten. Jetzt ist der kürzeste Weg zum Ziel endgültig und du darfst stoppen.

Den Weg rückwärts aufbauen

Folge vom Ziel aus den Vorgängern:

H ← G ← C ← D

Drehe die Reihenfolge um:

D → C → G → H

Die Gesamtkosten sind $3+2+4=9$.

Dijkstra trifft eine Greedy-Entscheidung: Der momentan billigste offene Knoten wird endgültig geschlossen. Bei nichtnegativen Gewichten kann jede zusätzliche Kante die Kosten nur beibehalten oder erhöhen. Ein späterer Umweg kann deshalb einen bereits minimal ausgewählten Knoten nicht billiger erreichen.

Bei einer negativen Kante bricht diese Begründung zusammen: Ein zunächst teurer wirkender Weg kann seine Kosten später stark senken. Dijkstra öffnet einen endgültig geschlossenen Knoten jedoch nicht erneut und kann dadurch einen falschen Weg liefern. Für Graphen mit negativen Kanten ist beispielsweise Bellman-Ford vorgesehen.

Ein negativer Zyklus ist ein Rundweg mit negativer Gewichtssumme. Kann er beliebig oft auf einem Weg durchlaufen werden, sinken die Kosten immer weiter. Dann gibt es keinen endlichen kürzesten Weg.

Die Vorgänger können einen Kürzeste-Wege-Baum vom Start bilden. Dieser ist nicht dasselbe wie ein minimaler Spannbaum:

• Ein Kürzeste-Wege-Baum enthält günstigste Wege von einem festgelegten Start.
• Ein minimaler Spannbaum verbindet alle Knoten mit möglichst kleiner Summe seiner Baumkanten.

Auch die Breitensuche löst ein anderes Problem: Sie minimiert die Zahl der Kanten. Nur bei gleichen Kantengewichten stimmt diese Bewertung mit den gewichteten Wegkosten überein.