Der Dijkstra-Algorithmus verständlich erklärt

Wer die schnellste Route von einem Lager zu einem Kunden sucht, braucht ein Verfahren, das nicht nur Strecken zählt, sondern Kosten wie Fahrminuten. Der Dijkstra-Algorithmus ist das klassische Verfahren dafür: Er legt die Orte nacheinander endgültig fest, immer den mit den bisher geringsten Kosten. Das stimmt aber nur, solange keine Strecke negative Kosten hat. Diese Seite erklärt zuerst ohne Formeln, warum das funktioniert und wo es endet, und danach für Fachleute mit Modell, Formeln, Messwerten und Grenzen. Sie ist zugleich der Einstieg in die Themenreihe „Kürzeste Wege“ auf dieser Website.

Zuletzt aktualisiert: 28. Oktober 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Die schnellste Route hat nicht die wenigsten Strecken

Stellen Sie sich ein Liefernetz vor: ein Lager, mehrere Orte dazwischen und ein Kunde. Zwischen manchen Orten gibt es eine Straße, und jede Straße braucht eine bestimmte Fahrzeit. Solche Netze aus Orten und Verbindungen heißen bei Fachleuten Graphen, die Orte Knoten und die Verbindungen Kanten. Hier sprechen wir von Orten und Strecken, und die Fahrzeit einer Strecke nennen wir ihre Kosten.

Gesucht ist die Route vom Lager zum Kunden mit den geringsten Gesamtkosten. Das ist nicht automatisch die Route mit den wenigsten Strecken. Zwei Strecken, von denen eine über eine verstopfte Landstraße führt, können länger dauern als ein Umweg über drei Strecken, die alle zügig befahrbar sind. Die Breitensuche, ein Verfahren, das nur Strecken zählt und Fahrzeiten ignoriert, findet deshalb nicht immer die schnellste Route. Und an jedem Ort einfach die gerade billigste Strecke zu nehmen, kann sogar weit in die Irre führen.

Die Idee: Orte der Reihe nach endgültig festlegen

Der Dijkstra-Algorithmus ist eine Rechenvorschrift, die genau dieses Problem löst. Stellen Sie sich einen Notizzettel vor. Neben jedem Ort steht, wie lange die beste bisher bekannte Fahrt vom Lager dorthin dauert. Am Anfang kennt man nur das Lager, dort steht null. Alle anderen Orte gelten als unendlich weit weg, weil noch keine Fahrt zu ihnen bekannt ist.

Dann wiederholt sich ein einfacher Schritt. Unter den Orten, die noch nicht abgehakt sind und schon einen Wert auf dem Zettel haben, wählen Sie den mit dem kleinsten Wert und haken ihn endgültig ab. Anschließend schauen Sie sich dessen Nachbarn an: Fährt man über den eben abgehakten Ort zu einem Nachbarn, ist das vielleicht schneller als der bisherige Zettelwert. Wenn ja, tragen Sie den besseren Wert ein und merken sich, über welchen Ort man kam. Die Werte der noch offenen Orte können sich also unterwegs verbessern. Ein abgehakter Ort ändert sich nicht mehr.

Warum darf man den Ort mit dem kleinsten Zettelwert endgültig abhaken? Jede andere Route zu ihm würde zuerst über einen Ort führen, der noch nicht abgehakt ist. Dieser hat einen größeren Zettelwert, ist also weiter entfernt. Von dort kann es nur noch länger werden, denn eine angehängte Strecke macht eine Fahrt nie kürzer. So werden die Orte in der Reihenfolge ihrer Entfernung vom Lager festgelegt, ähnlich wie sich Wellen von einem Stein im Teich ausbreiten. Sobald der Kunde abgehakt ist, ist die Suche fertig, und die Route ergibt sich rückwärts über die gemerkten Vorgänger.

Wann die Idee bricht: negative Kosten

Der Satz „eine Fahrt wird nicht schneller, wenn man eine Strecke anhängt“ stimmt nur, solange keine Strecke negative Kosten hat. Bei Fahrzeiten und Entfernungen ist das immer so. Es gibt aber Netze, in denen eine Strecke Geld zurückbringt. Ein Vergleich aus der Logistik: Eine Rückfuhr, die mehr einbringt, als sie kostet, wirkt wie eine Strecke mit negativen Kosten. Die Demo zeigt das an einem anderen Beispiel: Fahrradteile tauschen. Jeder Tausch ist eine Strecke von einem Gegenstand zum nächsten, und ein Tausch mit Rückzahlung ist eine Strecke mit negativen Kosten, weil man dabei Geld zurückbekommt.

Dann kann ein Umweg über die Rückzahlung billiger sein als ein Ort, den der Algorithmus schon endgültig abgehakt hat. Er fasst diesen Ort aber nicht mehr an, weil er sich auf die Endgültigkeit verlassen hat, und liefert eine Route, die teurer ist als die beste. Die Demo meldet in solchen Fällen einen Alarm und zeigt, wo die Festlegung nicht endgültig war. Ohne negative Strecken geht das nie schief. In den Zufallsnetzen der Demo genügen schon wenige negative Strecken, damit Dijkstra gelegentlich falsch liegt.

Für solche Netze braucht man ein anderes Verfahren. Das Verfahren Bellman-Ford prüft Runde für Runde alle Strecken und kommt deshalb auch mit negativen Kosten zurecht.

Der Preis: Dijkstra sucht in alle Richtungen

Dijkstra ist verlässlich, aber nicht schlau. Er weiß nicht, in welcher Richtung der Kunde liegt, und legt alle Orte fest, die näher am Lager liegen als der Kunde, auch die in der falschen Richtung. Das ist wie ein Suchtrupp, der gleichmäßig in alle Richtungen ausschwärmt. In der Demo ist das bei einem typischen Paar aus Start und Ziel ein großer Teil des Netzes, bevor die Suche endet. Außerdem beginnt jede neue Anfrage wieder von vorn.

Gegen diese Schwächen gibt es andere Verfahren, die von beiden Enden suchen, Wege vorab vorrechnen oder mit negativen Kosten umgehen; sie behandeln die weiteren Demos der Reihe.

Wie ernst ist das Modell zu nehmen?

Die Demo zeigt ein einziges Verfahren an kleinen und größeren Beispielnetzen. Die kleinen Netze sind ausgedachte Graphen mit eigenen Zahlen, ein Netz besteht aus echten Kartendaten, die übrigen werden erzeugt. Alle Kosten sind feste, ganze Zahlen, die sich während der Suche nicht ändern. Fahrzeiten, die mit der Tageszeit schwanken, bildet die Demo deshalb nicht ab. Die Demo zeigt, wie das Verfahren arbeitet und wo es an Grenzen stößt, nicht wie sich ein bestimmtes echtes Liefernetz verhält.

Was Sie mitnehmen: Sind alle Kosten null oder positiv, wie bei Fahrzeiten und Entfernungen, liefert Dijkstra die billigste Route. Gibt es Rückzahlungen, Gutschriften oder Ähnliches, die Kosten senken, prüfen Sie vor dem Einsatz, ob das Verfahren noch passt.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.

• Modell: gerichteter Graph \(G=(V,E)\) mit Kantenkosten \(c_e \ge 0\) (in dieser Demo ganzzahlig: Meter, Minuten oder Euro), Start \(s\); \(\delta(v)\) sind die Kosten einer billigsten Route von \(s\) nach \(v\). Ein Ziel \(t\) beendet die Suche, sobald es festgelegt ist.
• Verfahren: vorläufige Entfernungen \(d(v)\), zu Beginn \(d(s)=0\) und sonst \(\infty\); Menge \(S\) der festgelegten Knoten, zu Beginn leer. Die Warteschlange enthält die Knoten mit bekannter, aber noch nicht festgelegter Entfernung. Die Voreinstellung ist ein Binärheap mit Decrease-Key; fünf Warteschlangen sind austauschbar (Feld, Binärheap, fauler Heap, Dial-Eimer, Fibonacci-Heap).
• Beispielnetze: Lieferwege (7 Orte, Fahrminuten), Tausch mit Rückzahlung (Fahrradteile, ein Tausch mit Rückzahlung ist eine negative Kante), Rohdaten-Falle (3 Knoten mit Parallelkante und Schleife), Toronto Campus (OpenStreetMap-Auszug mit 5 072 Knoten und 14 503 gerichteten Kanten, Kosten auf ganze Meter gerundet), Stadtnetz und Labyrinth (erzeugt, mit Größen- und Kostenreglern).

Die Formeln

Der Kern ist die Relaxation: Wird \(u\) festgelegt, verbessert Dijkstra für jeden Nachbarn \(v\) die vorläufige Entfernung.

\[d(v) \leftarrow \min\big(d(v),\ d(u)+c_{uv}\big)\]

Die Invariante lautet: Für jeden Knoten \(u \in S\) gilt \(d(u)=\delta(u)\), und für jeden anderen Knoten ist \(d(v)\) die Länge einer billigsten Route, die außer dem Endknoten nur Knoten in \(S\) benutzt. Beweisidee: Angenommen, \(d(u) > \delta(u)\) beim Festlegen von \(u\). Auf einer billigsten Route zu \(u\) gibt es den ersten Knoten \(y \notin S\); sein Vorgänger liegt in \(S\), also gilt \(d(y)=\delta(y)\). Wegen \(c_e \ge 0\) folgt

\[\delta(y) \le \delta(u) < d(u)\]

und \(y\) hätte vor \(u\) gewählt werden müssen. Bei einer negativen Kante bricht genau der Schritt \(\delta(y) \le \delta(u)\), denn eine Route kann billiger werden, wenn man Kanten anhängt. Der Alarm der Demo ist ein festgelegter Knoten \(v\) mit einer Verbesserung \(d(u)+c_{uv}<d(v)\); Dijkstra bessert nicht nach (so wird es gelehrt), das Ergebnis ist dann falsch.

Der Aufwand hängt von der Warteschlange ab: \(|V|\) Einfügungen und Entnahmen, höchstens \(|E|\) Verkleinerungen. Beim Binärheap ergibt das

\[O((|V|+|E|)\log|V|)\]

Der Fibonacci-Heap kommt auf \(O(|E|+|V|\log|V|)\), die Dial-Eimer bei ganzzahligen Kosten bis \(C\) auf \(O(|E|+C|V|)\), das Feld im schlimmsten Fall auf \(O(|V|^2)\). Beim Abbruch am Ziel \(t\) sind genau die Knoten mit \(\delta(v) < \delta(t)\) festgelegt (plus einige mit Gleichstand). Für ein zufälliges Ziel ist die Rangzahl von \(\delta(t)\) gleichverteilt, der erwartete festgelegte Anteil also etwa \(\tfrac12\). In der Ebene enthält der Kostenradius \(L\) etwa \(\pi L^2\) Fläche, die Zahl festgelegter Knoten wächst wie \(L^2\).

Bei gleichen Kosten (\(c_e \equiv 1\)) ist die Warteschlange eine gewöhnliche Schlange: Dijkstra legt die Knoten in der Reihenfolge der Breitensuche fest.

Befunde

Alle Zahlen stammen aus der README der Demo (jede steht in deren Tests, tests/test_claims.py). Das Stadtnetz hat 20 × 20 Kreuzungen, Reichweite 2,3, Streuung 1,0; Paarstatistiken beruhen auf 200 zufälligen Start-Ziel-Paaren, die Netzstatistik auf fünf festen Netzen, das Experiment mit negativen Kanten auf 200 Netzen je Anteil und 5 festen Datensätzen. Ausnahmen sind genannt.

Frage	Befund
Findet Dijkstra die billigste Route, wo die Breitensuche scheitert? (Lieferwege)	Dijkstra findet 9 Minuten über drei Strecken; die Breitensuche (zwei Strecken) käme auf 12, „immer die billigste Kante“ auf 30. Zwei vorläufige Entfernungen werden unterwegs verbessert (Brücke 9 → 6, Kunde 14 → 9).
Wie viel länger ist die Route der Breitensuche? (Stadtnetz)	Dijkstra findet 3 186 m, die Route der Breitensuche ist 27 % länger. Median-Umweg der Breitensuche über 200 Paare 24 % (im Mittel über fünf feste Netze 28 %; Dijkstra: immer 0).
Wie viel des Netzes legt Dijkstra fest, bevor das Ziel feststeht?	Bei einem typischen Paar rund die Hälfte des Netzes (Stadtnetz: Median 51 %, bei einem Zehntel der Paare über 85 %). Toronto Campus: 891 m statt 1 129 m der Breitensuche (27 % weniger), dafür 2 513 von 5 072 Knoten festgelegt; über 200 Paare Median 51 %.
Wie wächst die Zahl der festgelegten Knoten mit der Entfernung?	Von der Mitte eines Netzes aus mit L hoch 2,08 (Steigung im Log-Log, im Inneren gemessen), wie die Fläche eines Kreises. Der festgelegte Anteil ist bei zufälligen Paaren etwa gleichverteilt, im Mittel also die Hälfte, unabhängig von Größe und Form.
Was passiert bei gleichen Kosten? (Labyrinth)	Dijkstra legt genau die Schichten der Breitensuche fest (in fünf festen Netzen geprüft), gleiche Route mit 42 Schritten.
Was kostet eine negative Kante? (Tausch mit Rückzahlung)	Dijkstra findet 16 Euro, die beste Route kostet 13 (23 % zu viel); der Alarm zeigt, wo die Festlegung nicht endgültig war.
Wie oft geht Dijkstra in Zufallsnetzen schief?	Ohne negative Kanten nie; bei 2 % negativer Kanten liefert er in etwa jedem fünften Netz (20 %) falsche Kosten. Mit vielen negativen Kanten überwiegen negative Zyklen (200 Netze je Anteil, 5 feste Datensätze).
Spielt die Warteschlange eine Rolle?	Alle fünf Umsetzungen liefern dieselben Entfernungen. Jeder Knoten wird einmal eingefügt, etwa jeder zweite bekommt einen Decrease-Key. Der Fibonacci-Heap braucht rund 17 % weniger Schlüsselvergleiche als der Binärheap, ist in dieser Python-Umsetzung aber nicht spürbar schneller (Laufzeiten sind Messwerte, nicht getestet); das Feld wächst hier wie n hoch 1,5, die Heaps kaum stärker als linear.
Was können Rohdaten anrichten?	Ein Netz mit Parallelkanten: Mehrfachkanten-Graph und bereinigte Daten liefern 3; ein Wörterbuch je Knotenpaar liefert 3 oder 7, je nach Reihenfolge der Rohdaten.

Grenzen

• Nur nichtnegative Kosten: Die Korrektheit gilt nur für \(c_e \ge 0\). Die Bellman-Ford-Referenz in der Demo ist ein Messwerkzeug; das Verfahren selbst ist ein eigenes Stück der Linie.
• Anteil festgelegter Knoten: Die Hälfte gilt im Mittel über zufällige Paare. Für ein einzelnes Paar kann der Anteil beliebig zwischen fast nichts und fast allem liegen (bei einem Zehntel der Paare über 85 %). Welcher Zufalls-Seed das Beispiel von 3 186 m erzeugt, nennt die README nicht.
• Beispielnetze: Die kleinen Netze sind eigene Graphen mit eigenen Zahlen und folgen den Büchern nur in der Idee; Toronto Campus ist ein OpenStreetMap-Auszug, die Kosten sind auf ganze Meter gerundet. Aussagen gelten für diese Netze und Regler.
• Laufzeiten: Sie sind Messwerte dieser Python-Umsetzung und schwanken; belegt sind nur die Zähler. Dass sich der Fibonacci-Heap erst bei sehr dichten Netzen auszahlt, ist die theoretische Schranke, kein Ergebnis der Demo.
• Nicht enthalten: Suche von beiden Enden, zielgerichtete Suche, Vorrechnung (Contraction Hierarchies), negative Kanten (Bellman-Ford), alle Paare (Floyd-Warshall, Johnson) und mehrere Kriterien; ebenso fehlen zeitabhängige Kosten (die Kosten sind feste ganze Zahlen). Jedes dieser Verfahren hat ein eigenes Stück der Linie; A* steht in der Baumsuche-Linie.

Quellen

• Dijkstra, E. W. (1959): A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271.
• Fredman, M. L., Tarjan, R. E. (1987): Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM 34(3), 596–615.
• Bhargava, A.: Grokking Algorithms, Kap. 9 (Idee der kleinen Beispielnetze; Graphen und Zahlen der Demo sind eigene).
• Khamis, A.: Optimization Algorithms, Kap. 3 (Idee der Rohdaten-Falle und des Toronto-Szenarios).
• Quelltext, Beispielnetze und Tests der Demo: github.com/sebastian-hanisch/dijkstra-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen. Die beiden Bücher stammen aus der README der Demo; die Angaben zu Dijkstra (1959) und Fredman und Tarjan (1987) stammen aus dem Gedächtnis des Autors und sind nicht gegen die Originale geprüft.