Dijkstra-Algorithmus — Kürzester Pfad Schritt für Schritt

Der Dijkstra-Algorithmus findet kürzeste Wege von einem Startknoten in einem gewichteten Graphen, solange jedes Kantengewicht nichtnegativ ist. Wenn dich nur ein bestimmtes Ziel interessiert, kannst du aufhören, sobald dieser Zielknoten abgeschlossen ist.

Der zentrale Schritt ist gierig: Man macht immer beim noch nicht abgeschlossenen Knoten mit der kleinsten bekannten Distanz weiter. Das funktioniert nur unter der Bedingung, dass alle Gewichte nichtnegativ sind.

Was der Dijkstra-Algorithmus löst

Verwende den Dijkstra-Algorithmus, wenn du einen Graphen mit Kosten auf den Kanten hast und die billigste Route finden willst. Die Kosten können Entfernung, Reisezeit, Energie oder eine andere Größe darstellen, die du minimieren möchtest.

Er funktioniert auf gerichteten und ungerichteten Graphen. Die entscheidende Bedingung ist klar: Jedes Kantengewicht muss mindestens $0$ sein.

Wie der Algorithmus funktioniert

Jeder Knoten speichert eine vorläufige Distanz vom Startknoten. Am Anfang hat der Startknoten die Distanz $0$ und jeder andere Knoten die Distanz $\infty$.

Dann wird diese Schleife wiederholt:

1. Wähle den noch nicht abgeschlossenen Knoten mit der kleinsten vorläufigen Distanz.
2. Prüfe jeden Nachbarn über diesen Knoten.
3. Wenn die neue Route günstiger ist, aktualisiere die Distanz des Nachbarn.
4. Markiere den aktuellen Knoten als abgeschlossen.

Schritt 3 heißt Relaxation. Ein abgeschlossener Knoten ist fertig: Seine kürzeste Distanz steht endgültig fest, vorausgesetzt, der Graph hat keine negativen Kantengewichte.

Dijkstra-Algorithmus Schritt für Schritt

Hier ist das vollständige Verfahren in kompakter Form:

1. Wähle einen Startknoten.
2. Setze seine Distanz auf $0$ und jede andere Distanz auf $\infty$.
3. Wähle den noch nicht abgeschlossenen Knoten mit der kleinsten vorläufigen Distanz.
4. Entspanne seine ausgehenden Kanten.
5. Markiere diesen Knoten als abgeschlossen.
6. Wiederhole das Ganze, bis alle erreichbaren Knoten abgeschlossen sind, oder stoppe, sobald dein Zielknoten abgeschlossen ist.

Wenn du zusätzlich speicherst, welcher vorherige Knoten jede Aktualisierung verursacht hat, kannst du den tatsächlichen Pfad rekonstruieren und nicht nur die Enddistanz.

Durchgerechnetes Beispiel für den kürzesten Pfad

Angenommen, der Graph hat diese Kantengewichte:

• $A \to B = 4$
• $A \to C = 1$
• $C \to B = 2$
• $B \to D = 1$
• $C \to D = 5$

Wir wollen den kürzesten Pfad von $A$ nach $D$ finden.

Starte mit:

$$\text{dist}(A)=0,\quad \text{dist}(B)=\infty,\quad \text{dist}(C)=\infty,\quad \text{dist}(D)=\infty$$

Schließe zuerst $A$ ab und entspanne seine Kanten:

$$\text{dist}(B)=4,\quad \text{dist}(C)=1$$

Die kleinste noch nicht abgeschlossene Distanz liegt jetzt bei $C$, also schließen wir als Nächstes $C$ ab.

Über $C$ gilt:

• Über $C$ kostet der Pfad nach $B$ $1+2=3$, das ist besser als $4$, also aktualisieren wir $\text{dist}(B)=3$.
• Über $C$ kostet der Pfad nach $D$ $1+5=6$, also setzen wir $\text{dist}(D)=6$.

Jetzt hat $B$ die kleinste noch nicht abgeschlossene Distanz, also schließen wir $B$ ab.

Über $B$ kostet der Pfad nach $D$:

$$3+1=4$$

Das ist besser als $6$, also aktualisieren wir $\text{dist}(D)$ von $6$ auf $4$.

Jetzt ist $D$ der noch nicht abgeschlossene Knoten mit der kleinsten Distanz. Schließe ihn ab und stoppe.

Der kürzeste Pfad ist:

$$A \to C \to B \to D$$

mit Gesamtkosten:

$$1+2+1=4$$

Dieses Beispiel zeigt das zentrale Muster: Eine Route, die zuerst schlechter aussah, $A \to B$, wurde später über $C$ besser. Der Dijkstra-Algorithmus erlaubt das, solange $B$ noch nicht abgeschlossen ist. Sobald ein Knoten abgeschlossen ist, ändert sich seine Distanz nicht mehr.

Warum nichtnegative Gewichte wichtig sind

Angenommen, der aktuell billigste noch nicht abgeschlossene Knoten hat die Distanz $d$. Jeder neue Pfad zu diesem Knoten, der erst später gefunden wird, müsste von einem anderen noch nicht abgeschlossenen Knoten kommen, dessen vorläufige Distanz mindestens $d$ ist, und dann noch eine Kante mit Gewicht mindestens $0$ hinzufügen.

Deshalb kann dieser spätere Weg $d$ nicht unterbieten. Genau darum ist es sicher, immer die kleinste vorläufige Distanz abzuschließen, wenn alle Gewichte nichtnegativ sind.

Falls es eine negative Kante gibt, bricht dieses Argument zusammen. Ein Pfad, der jetzt teuer aussieht, kann später billiger werden. Dann kann das zu frühe Abschließen eines Knotens zur falschen Antwort führen.

Häufige Fehler beim Dijkstra-Algorithmus

Verwendung bei einer negativen Kante

Schon eine einzige negative Kante kann die gierige Logik zerstören. Wenn negative Gewichte möglich sind, solltest du ein anderes Verfahren für kürzeste Pfade verwenden.

"Gesehen" mit "fertig" verwechseln

Ein Knoten kann bereits eine vorläufige Distanz haben und trotzdem noch nicht fertig sein. Nur ein abgeschlossener Knoten hat eine endgültige kürzeste Distanz.

Die Vorgängertabelle vergessen

Distanzen geben dir die Kosten. Wenn du auch die Route selbst haben willst, speichere, welcher Knoten zuletzt jede Distanz verbessert hat.

Wo der Dijkstra-Algorithmus verwendet wird

Der Dijkstra-Algorithmus wird verwendet, wenn sich ein Problem als Bewegung durch einen Graphen mit nichtnegativen Kosten modellieren lässt:

• Routenplanung auf Karten
• Netzwerk-Routing
• Roboterbewegung auf gewichteten Gittern
• Pfadsuche in Spielen, wenn sich Bewegungskosten unterscheiden

Er ist außerdem ein Standardbeispiel für einen gierigen Algorithmus, dessen Korrektheit von einer präzisen Bedingung abhängt.

Probiere ein ähnliches Problem

Zeichne einen Graphen mit fünf Knoten und positiven Kantengewichten und führe den Dijkstra-Algorithmus von Hand mit einer Distanztabelle aus. Wenn du einen guten nächsten Schritt suchst, probiere deine eigene Variante auf einem neuen Graphen aus und prüfe genau, wann jeder Knoten sicher abgeschlossen werden kann.