Dijkstra-Algorithmus

Beobachte, wie der Dijkstra-Algorithmus den kürzesten Pfad in einem gewichteten Graphen findet.

Rechenbeispiel — Dijkstra-Algorithmus

Knoten 0	0
Knoten 1	3
Knoten 2	8
Knoten 3	2
Knoten 4	8
Kürzester Pfad	0 → 3 → 4 (cost: 8)

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Die Relaxation ist der ganze Algorithmus; die Prioritätswarteschlange ist nur Geschwindigkeit 🖖

Der Dijkstra-Algorithmus findet den kürzesten Pfad in einem Graphen mit nicht-negativen Kantengewichten. Er arbeitet gierig (greedy) und aktualisiert Pfade durch Relaxation: d(v) = min(d(v), d(u) + w(u,v)). Mit einer Fibonacci-Heap-Prioritätswarteschlange wird die Laufzeit auf O(E + V log V) optimiert.

Warum der nächste Knoten immer sicher ist 🖖

Dijkstra lässt eine Front vom Startknoten nach außen wachsen und wählt stets den nächstgelegenen noch nicht besuchten Knoten aus. Da jedes Kantengewicht nicht-negativ ist, kann kein späterer Umweg eine bereits gefundene kürzere Strecke unterbieten — sobald ein Knoten festgelegt ist, ist seine Distanz endgültig und wird nie erneut geprüft. Deshalb verlassen sich Routenplaner und Internet-Routingprotokolle wie OSPF darauf, um zuverlässige kürzeste Wege zu berechnen.

In zwanzig Minuten beim Kaffee erdacht 🖖

Edsger Dijkstra ersann den Algorithmus 1956 in etwa zwanzig Minuten, ganz ohne Bleistift und Papier, während er sich auf der Terrasse eines Amsterdamer Cafés ausruhte. Er suchte ein Demonstrationsproblem für den Rechner ARMAC und wählte die kürzeste Route zwischen den niederländischen Städten Rotterdam und Groningen. Drei Jahre später veröffentlichte er ihn in einem kaum dreiseitigen Aufsatz — einem der meistzitierten Ergebnisse der Informatik.

Aufgabe vollständig gelöst

Knoten 1 eine Kante von der Quelle entfernt mit Kosten von 4 5 Schritte
Knoten 1 ist eine Kante vom Startknoten entfernt, mit Kosten von 4 – und der Algorithmus gibt seine Distanz mit 3 an. Gehen Sie die Reihenfolge des Abschließens durch und finden Sie heraus, woher die 3 kommt.
1. Dijkstra schließt Knoten in der Reihenfolge ihrer Distanz ab und besucht sie nie erneut. Diese Reihenfolge ist der gesamte Algorithmus und der gesamte Beweis: Wenn ein Knoten abgeschlossen ist, kann kein günstigerer Weg zu ihm existieren, da jeder solche Weg über einen noch nicht abgeschlossenen Knoten führen müsste, der bereits weiter entfernt ist.
  
  $E = {(0, 1, 4), (0, 3, 2), (1, 2, 5), (1, 3, 1), (2, 4, 3), (3, 4, 6)}$
2. Vom Startknoten aus liefern die zwei direkten Kanten vorläufige Distanzen von 4 und 2. Keine von beiden ist bereits final – sie sind obere Schranken.
  
  $settle 0 : d_{1} = 4, d_{3} = 2$
3. Der nächstgelegene ist Knoten 3 mit 2, daher wird er zuerst abgeschlossen. Das Relaxieren seiner Kanten findet einen Weg zu Knoten 1 mit den Kosten 2 + 1 = 3, was die direkte Kante von 4 unterbietet. Dies ist der Schritt, der die Frage beantwortet: Der günstigste Weg zu einem Nachbarn muss nicht die Kante zu ihm sein.
  
  $settle 3 (d = 2) : d_{1} = min (4, 2 + 1) = 3, d_{4} = 2 + 6 = 8$
4. Knoten 1 wird bei 3 abgeschlossen, und das Relaxieren von dort aus erreicht Knoten 2 bei 8.
  
  $settle 1 (d = 3) : d_{2} = 3 + 5 = 8$
5. Knoten 4 ist über Knoten 3 bei 8 erreichbar, und die Alternative über Knoten 2 kostet 8 + 3 = 11, sodass der kürzere Weg bestehen bleibt.
  
  $settle 2, 4 : d_{4} = min (8, 8 + 3) = 8 ⟹ 0 \to 3 \to 4$
Antwort

Das Werkzeug gibt Distanzen von 3, 8, 2, 8 und einen kürzesten Pfad von 0 → 3 → 4 aus. Die Lehre liegt in Knoten 1: Eine direkte Kante ist kein kürzester Pfad, und gieriges Abschließen macht das Herausfinden günstig statt exponentiell. Die Garantie hat jedoch eine Voraussetzung – nicht-negative Gewichte. Mit einer negativen Kante kann ein früh abgeschlossener Knoten später noch verbessert werden, und der Beweis aus Schritt 1 bricht zusammen. Klicken Sie auf die Voreinstellung für negative Kanten und beobachten Sie, wie der Algorithmus auf beide Arten gleichzeitig scheitert: Knoten 3 kommt mit −1 zurück, was keine Distanz ist, die irgendein Weg erzeugt, und die Pfadrekonstruktion gibt mit „Kein Pfad – die Vorgänger bilden eine Schleife“ völlig auf. Falsche Zahlen und kein Pfad – von einem Algorithmus, der nachweislich korrekt ist, sobald jedes Gewicht nicht-negativ ist.

$d_{1} = 3 via node 3, not 4 direct; 0 \to 3 \to 4 = 8$

Quellen (2)

The three-page paper, in which the shortest-path algorithm is the SECOND of the two problems: E. W. Dijkstra, "A note on two problems in connexion with graphs." Numerische Mathematik 1, 269–271, 1959.
The algorithm the negative-edge preset points you to, which tolerates negative weights and detects a negative cycle instead of answering as though there were none: R. Bellman, "On a routing problem." Quarterly of Applied Mathematics 16(1), 87–90, 1958.

Vom 42Math-Team · Aktualisiert 2026-06-11

Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen. Redaktionsrichtlinie · Korrekturen

Alle Lektionen: Informatik →

Beispielaufgaben

5-Knoten-Stadt - Stadt mit 5 Knoten: kürzester Pfad 0→4
3×3-Gitter - 3×3-Gitter: mehrere kürzeste Pfade
Tief vs. breit - Tief vs. breit: Greedy-Ansatz scheitert
Negative Kante - Negative Kante: Dijkstra kann versagen