FACHARTIKEL
Ohne Umwege
Edsger W. Dijkstra wollte eigentlich theoretischer Physiker werden. Erst ein Gespräch mit dem Mathematiker Adriaan van Wijngaarden lenkte ihn zur Informatik – einer Wissenschaft, die damals gerade erst im Entstehen war. Und das ist gut so: Hätte er diesen Weg nicht eingeschlagen, müssten wir in der Informatik womöglich bis heute noch so manchen – zumindest gedanklichen – Umweg nehmen.
1956 entwickelte Dijkstra seinen Algorithmus, um auf einer stilisierten Landkarte den schnellsten Weg zwischen Städten zu berechnen, als anschauliche Demonstration für einen neuen Computer. Die Idee entstand beim Kaffeetrinken mit seiner Verlobten. Veröffentlicht wurde der Algorithmus 1959 in einem kurzen, aber wegweisenden Artikel. Heute zählt er zu den Klassikern der Informatik, alle Weiterentwicklungen des Single-Source Shortest Paths Routing berufen sich auf das, was Dijkstra damals veröffentlicht hat. Grund genug, sich die Funktionsweise etwas genauer anzuschauen.
Stellen wir uns vor, wir möchten mit dem Zug von Berlin nach München reisen und kennen zwar die Verbindungen zwischen den Städten, aber nicht den besten Weg. Der Dijkstra-Algorithmus geht dieses Problem Schritt für Schritt an: Er beginnt in Berlin und sucht zunächst alle direkten (Nachbar-)städte, die ohne Zwischenhalt direkt erreichbar sind. Von dort aus erkundet er systematisch alle erreichbaren Orte, wobei er stets die aktuell kürzeste bekannte Strecke im Blick behält. So entsteht eine Art Suchbaum, dessen erkundeter Teil sich wie eine Wellenfront ausbreitet – bis schließlich München erreicht ist. Wie das konkret funktioniert, zeigen wir am Beispiel der Städte Berlin, Leipzig, Jena, Nürnberg, Augsburg und München.
Die Eingabe für den Dijkstra-Algorithmus ist im einfachsten Fall ein ungerichteter, gewichteter Graph: eine Menge von Knoten, verbunden durch Kanten, die in Hin- und Rückrichtung zu jeweils gleichen Kosten (Entfernung, Reisezeit oder Ähnliches – solange es nur als eine Zahl dargestellt werden kann, die größer als 0 ist) durchlaufen werden können. Für die folgenden Beispiele betrachten wir die Reisezeit in Minuten.
Der erste Schritt ist somit die Auswahl der Stadt, in der die Reise beginnt. Der Dijkstra-Algorithmus bestimmt den kürzesten Weg nicht nur zu einer Stadt, sondern zu allen Städten, die im Graphen enthalten sind. (Die Leserin ist eingeladen, sich zu überlegen, welche Änderungen nötig sind, um den Ablauf an der richtigen Stelle abzubrechen, wenn tatsächlich nur der kürzeste Weg zu einer Stadt gesucht ist.)
Für jeden Knoten S im Graphen G, also jede Stadt, merken wir uns:
- visited[S] : ob S bereits besucht wurde (true oder false)
- d[s] : die derzeit kürzeste bekannte Distanz von start nach S
- parent[S] : den Vorgängerknoten von S auf einem solchen kürzesten Weg, sofern bekannt – ansonsten unbestimmt
Damit können wir den Algorithmus formulieren:
Dijkstra(G, start) BEGIN // Initialisierung FOR ALL Knoten u in G DO markiere den Knoten u als unbesucht d[u] := unendlich parent[u] := unbestimmt ENDFOR d[start] := 0 WHILE es unbesuchte Knoten gibt DO v := ein unbesuchter Knoten mit minimalem d[v] markiere den Knoten v als besucht FOR ALL Nachbarn u von v DO IF d[v] + Gewicht(v,u) < d[u] THEN d[u] := d[v] + Gewicht(v,u) parent[u] := v ENDIF ENDFOR ENDWHILE END
Die Länge eines kürzesten Weges vom Startknoten zu einem beliebigen anderen Knoten ziel können wir nun in der Liste d ablesen, es ist der Wert d[ziel].
Den Weg selbst erhalten wir, indem wir die Liste der Vorgänger rückwärts durchlaufen.
BEGIN Pfad := leere Liste aktueller Knoten := ziel WHILE aktueller Knoten != unbestimmt DO Füge aktuellen Knoten am Anfang von Pfad ein aktueller Knoten := parent[aktueller Knoten] ENDWHILE Drucke Pfad aus Drucke d[ziel] aus END
[Initialisierung weglassen] Aufruf: dijkstra(netz, Berlin) Markiere Knoten Berlin als unbesucht. Markiere Knoten Leipzig als unbesucht. Markiere Knoten Jena als unbesucht. Markiere Knoten Nürnberg als unbesucht. Markiere Knoten Augsburg als unbesucht. Markiere Knoten München als unbesucht. Markiere Knoten Berlin als besucht. Nachbarn von Berlin gefunden: Leipzig, Jena Betrachte Nachbarn: Leipzig, Distanz: 75 Berechne neue Kosten für Leipzig: 0 + 75 = 75 Neue Kosten (75) sind geringer als aktuelle Kosten (unendlich) für Leipzig Verringere Kosten für Leipzig auf 75 Setze Vorgänger von Leipzig auf Berlin Betrachte Nachbarn: Jena, Distanz: 120 Berechne neue Kosten für Jena: 0 + 120 = 120 Neue Kosten (120) sind geringer als aktuelle Kosten (unendlich) für Jena Verringere Kosten für Jena auf 120 Setze Vorgänger von Jena auf Berlin Markiere Knoten Leipzig als besucht. Nachbarn von Leipzig gefunden: Berlin, Nürnberg Nachbar Berlin von Leipzig wurde bereits besucht. Betrachte Nachbarn: Nürnberg, Distanz: 150 Berechne neue Kosten für Nürnberg: 75 + 150 = 225 Neue Kosten (225) sind geringer als aktuelle Kosten (unendlich) für Nürnberg Verringere Kosten für Nürnberg auf 225 Setze Vorgänger von Nürnberg auf Leipzig Markiere Knoten Jena als besucht. Nachbarn von Jena gefunden: Berlin, Nürnberg Nachbar Berlin von Jena wurde bereits besucht. Betrachte Nachbarn: Nürnberg, Distanz: 105 Berechne neue Kosten für Nürnberg: 120 + 105 = 225 Keine Änderung für Nürnberg, da 225 >= 225 Markiere Knoten Nürnberg als besucht. Nachbarn von Nürnberg gefunden: Leipzig, Jena, Augsburg, München Nachbar Leipzig von Nürnberg wurde bereits besucht. Nachbar Jena von Nürnberg wurde bereits besucht. Betrachte Nachbarn: Augsburg, Distanz: 60 Berechne neue Kosten für Augsburg: 225 + 60 = 285 Neue Kosten (285) sind geringer als aktuelle Kosten (unendlich) für Augsburg Verringere Kosten für Augsburg auf 285 Setze Vorgänger von Augsburg auf Nürnberg Betrachte Nachbarn: München, Distanz: 75 Berechne neue Kosten für München: 225 + 75 = 300 Neue Kosten (300) sind geringer als aktuelle Kosten (unendlich) für München Verringere Kosten für München auf 300 Setze Vorgänger von München auf Nürnberg Markiere Knoten Augsburg als besucht. Nachbarn von Augsburg gefunden: Nürnberg, München Nachbar Nürnberg von Augsburg wurde bereits besucht. Betrachte Nachbarn: München, Distanz: 40 Berechne neue Kosten für München: 285 + 40 = 325 Keine Änderung für München, da 325 >= 300 Markiere Knoten München als besucht. Nachbarn von München gefunden: Nürnberg, Augsburg Nachbar Nürnberg von München wurde bereits besucht. Nachbar Augsburg von München wurde bereits besucht. Alle Knoten wurden besucht. Kürzester Weg von Berlin nach München: Berlin -> Leipzig -> Nürnberg -> München Kosten: 300
Dass der Dijkstra-Algorithmus stets vom selben Startpunkt ausgeht, ist für Anwendungen mit wechselnden Ausgangsorten, also zum Beispiel den klassischen Routenplaner, nicht ideal. Für feste Startorte, etwa einen Hafen, von dem aus Güter per Lkw verteilt werden, ist er dagegen gut geeignet.
Im Folgenden (siehe Tabelle) erweitern wir das Bahnhofsbeispiel: Bisher haben wir die Fahrzeit zwischen Städten betrachtet, aber dabei angenommen, dass keine Umstiege nötig sind. In der Realität ist das selten der Fall. Wer nicht gut zu Fuß ist, nimmt vielleicht lieber eine längere Reisezeit in Kauf, um seltener umsteigen zu müssen.
Auf der Fahrt von München nach Köln stehen die folgenden Linien zur Auswahl:
| Linie A | München → Augsburg | 35 |
| Augsburg → Ulm | 55 | |
| Ulm → Karlsruhe | 80 | |
| Karlsruhe → Koblenz | 150 |
| Linie B | Regensburg → Ingolstadt | 40 |
| Ingolstadt → Nürnberg | 50 | |
| Nürnberg → Würzburg | 60 | |
| Würzburg → Gießen | 85 | |
| Gießen → Dortmund | 95 |
| Linie C | Frankfurt → Mainz | 35 |
| Mainz → Koblenz | 60 | |
| Koblenz → Bonn | 60 | |
| Bonn → Köln | 20 |
| Linie D | Koblenz → Frankfurt | 60 |
| Frankfurt → Bonn | 50 |
| Weitere | Gießen → Frankfurt | 55 |
| Karlsruhe → Frankfurt | 70 | |
| Ulm → Mainz | 100 | |
| Ulm → Würzburg | 95 | |
| Ingolstadt → Augsburg | 70 |
Als Beispiel betrachten wir Koblenz, Frankfurt, Karlsruhe.
Zunächst hat das Streckennetz nur drei Knoten.
Wenn wir die Linie A nutzen, kommen wir in 150 Minuten direkt von Koblenz nach Karlsruhe. Wir könnten aber auch über Frankfurt fahren (also in einen Zug der Linie D umsteigen). Das dauert in der Summe nur 130 Minuten.
Den Ablauf des Algorithmus mit nur drei Knoten – Koblenz, Frankfurt, Karlsruhe – spiele der Leser zur Übung selbst durch. Im Ergebnis würden wir, wie nach einem Blick auf die Grafik auf der folgenden Seite sofort zu erkennen, in Frankfurt umsteigen. Wie lässt sich das verhindern?
Der Algorithmus hat als einzige Informationen die Fahrtdauern zwischen den Stationen. Er merkt sich zudem, welche Stationen er bereits besucht hat, und besucht diese nicht erneut.
Ein Ansatz besteht darin, in Frankfurt einen Aufenthalt künstlich in die Route aufzunehmen. Indem wir seine Dauer lang genug ansetzen, können wir das Umsteigen so unattraktiv machen, dass der Algorithmus eine Verbindung ohne Umsteigen bevorzugt. Dazu fügen wir zwei neue Knoten ein: Frankfurt an und Frankfurt ab. Zwischen ihnen fügen wir eine Kante ein, an die wir die Dauer des Aufenthalts schreiben. Zunächst wählen wir hier 10 Minuten. Die Kanten Koblenz → Frankfurt und Frankfurt → Karlsruhe entfernen wir, da der Algorithmus sonst stets die Verbindung ohne Aufenthalt wählen würde. Die Kante Koblenz → Karlsruhe bleibt bestehen, aber es gibt eine neue Kante Koblenz → Frankfurt, natürlich mit derselben Dauer wie vorher Koblenz → Frankfurt. Weiterhin gibt es eine neue Kante Frankfurt ab → Karlsruhe, mit derselben Dauer wie vorher Frankfurt → Karlsruhe.
[Initialisierung weglassen] Aufruf: dijkstra(netz, Koblenz) Markiere Knoten Koblenz als unbesucht. Markiere Knoten Karlsruhe als unbesucht. Markiere Knoten FrankfurtAn als unbesucht. Markiere Knoten FrankfurtAb als unbesucht. Markiere Knoten Koblenz als besucht. Nachbarn von Koblenz gefunden: Karlsruhe, FrankfurtAn Betrachte Nachbarn: Karlsruhe, Distanz: 150 Berechne neue Kosten für Karlsruhe: 0 + 150 = 150 Neue Kosten (150) sind geringer als aktuelle Kosten (unendlich) für Karlsruhe Verringere Kosten für Karlsruhe auf 150 Setze Vorgänger von Karlsruhe auf Koblenz Betrachte Nachbarn: FrankfurtAn, Distanz: 60 Berechne neue Kosten für FrankfurtAn: 0 + 60 = 60 Neue Kosten (60) sind geringer als aktuelle Kosten (unendlich) für FrankfurtAn Verringere Kosten für FrankfurtAn auf 60 Setze Vorgänger von FrankfurtAn auf Koblenz Markiere Knoten FrankfurtAn als besucht. Nachbarn von FrankfurtAn gefunden: Koblenz, FrankfurtAb Nachbar Koblenz von FrankfurtAn wurde bereits besucht. Betrachte Nachbarn: FrankfurtAb, Distanz: 10 Berechne neue Kosten für FrankfurtAb: 60 + 10 = 70 Neue Kosten (70) sind geringer als aktuelle Kosten (unendlich) für FrankfurtAb Verringere Kosten für FrankfurtAb auf 70 Setze Vorgänger von FrankfurtAb auf FrankfurtAn Markiere Knoten FrankfurtAb als besucht. Nachbarn von FrankfurtAb gefunden: FrankfurtAn, Karlsruhe Nachbar FrankfurtAn von FrankfurtAb wurde bereits besucht. Betrachte Nachbarn: Karlsruhe, Distanz: 70 Berechne neue Kosten für Karlsruhe: 70 + 70 = 140 Neue Kosten (140) sind geringer als aktuelle Kosten (150) für Karlsruhe Verringere Kosten für Karlsruhe auf 140 Setze Vorgänger von Karlsruhe auf FrankfurtAb Markiere Knoten Karlsruhe als besucht. Nachbarn von Karlsruhe gefunden: Koblenz, FrankfurtAb Nachbar Koblenz von Karlsruhe wurde bereits besucht. Nachbar FrankfurtAb von Karlsruhe wurde bereits besucht. Alle Knoten wurden besucht. Kürzester Weg von Koblenz nach Karlsruhe: Koblenz -> FrankfurtAn -> FrankfurtAb -> Karlsruhe Kosten: 140
Der Algorithmus wählt also die Verbindung über Frankfurt. Trotz des dortigen Aufenthalts ist sie schneller als die Direktverbindung.
Jetzt erhöhen wir die Dauer des Aufenthalts in Frankfurt auf 30 Minuten.
[Initialisierung weglassen] Aufruf: dijkstra(netz, Koblenz) Markiere Knoten Koblenz als unbesucht. Markiere Knoten Karlsruhe als unbesucht. Markiere Knoten FrankfurtAn als unbesucht. Markiere Knoten FrankfurtAb als unbesucht. Markiere Knoten Koblenz als besucht. Nachbarn von Koblenz gefunden: Karlsruhe, FrankfurtAn Betrachte Nachbarn: Karlsruhe, Distanz: 150 Berechne neue Kosten für Karlsruhe: 0 + 150 = 150 Neue Kosten (150) sind geringer als aktuelle Kosten (unendlich) für Karlsruhe Verringere Kosten für Karlsruhe auf 150 Setze Vorgänger von Karlsruhe auf Koblenz Betrachte Nachbarn: FrankfurtAn, Distanz: 60 Berechne neue Kosten für FrankfurtAn: 0 + 60 = 60 Neue Kosten (60) sind geringer als aktuelle Kosten (unendlich) für FrankfurtAn Verringere Kosten für FrankfurtAn auf 60 Setze Vorgänger von FrankfurtAn auf Koblenz Markiere Knoten FrankfurtAn als besucht. Nachbarn von FrankfurtAn gefunden: Koblenz, FrankfurtAb Nachbar Koblenz von FrankfurtAn wurde bereits besucht. Betrachte Nachbarn: FrankfurtAb, Distanz: 30 Berechne neue Kosten für FrankfurtAb: 60 + 30 = 90 Neue Kosten (90) sind geringer als aktuelle Kosten (unendlich) für FrankfurtAb Verringere Kosten für FrankfurtAb auf 90 Setze Vorgänger von FrankfurtAb auf FrankfurtAn Markiere Knoten FrankfurtAb als besucht. Nachbarn von FrankfurtAb gefunden: FrankfurtAn, Karlsruhe Nachbar FrankfurtAn von FrankfurtAb wurde bereits besucht. Betrachte Nachbarn: Karlsruhe, Distanz: 70 Berechne neue Kosten für Karlsruhe: 90 + 70 = 160 Keine Änderung für Karlsruhe, da 160 >= 150 Markiere Knoten Karlsruhe als besucht. Nachbarn von Karlsruhe gefunden: Koblenz, FrankfurtAb Nachbar Koblenz von Karlsruhe wurde bereits besucht. Nachbar FrankfurtAb von Karlsruhe wurde bereits besucht. Alle Knoten wurden besucht. Kürzester Weg von Koblenz nach Karlsruhe: Koblenz -> Karlsruhe Kosten: 150
Nach dieser Änderung sehen wir, dass die direkte Verbindung Koblenz → Karlsruhe gewählt wird.
Wer das Prinzip verstanden hat, ist eingeladen, es auf das große Liniennetz anzuwenden und sodann einen kürzesten Weg von München nach Köln zu finden. Hier hat man natürlich bei mehr als nur einem Bahnhof die Dauer des Aufenthalts zu wählen! Aufgrund der Vielzahl an infrage kommenden Möglichkeiten bieten wir keine Musterlösung an. Der Deep Dive bietet aber Gelegenheit, sich auszutoben!
Kürzlich ist es einem chinesischen Forschungsteam gelungen, den Dijkstra-Algorithmus erheblich zu verbessern. Ob diese neue Version sich tatsächlich durchsetzen wird, lässt sich noch nicht einschätzen. Fest steht jedoch schon heute, dass Beispiele wie in diesem Beitrag eine zentrale Botschaft vermitteln: Nicht selten ist Informatik die Lösung für alle, die auf der Suche nach neuen Wegen sind.
Deep Dive
[1] Ein sanfter Einstieg, auch für Schüler geeignet: algo.rwth-aachen.de/~algorithmus/Algorithmen/algo7/algo07.pdf
[2] Eine interaktive Visualisierung mit ausführlicher Erklärung: algorithms.discrete.ma.tum.de/graph-algorithms/spp-dijkstra/index_de.html
[3] Visualisierung mit schrittweisem Ablauf: www.cs.usfca.edu/~galles/visualization/Dijkstra.html
[4] Eine weitere Visualisierung: www.davbyjan.com
[5] Die Weiterentwicklung aus China (für Hartgesottene): arxiv.org/pdf/2504.17033
Der Dijkstra-Algorithmus
gehört zur Klasse der sogenannten Greedy-Algorithmen und löst das Problem der kürzesten Pfade für einen gegebenen Startknoten. Grundidee dabei ist es, immer derjenigen Kante zu folgen, die den kürzesten Streckenabschnitt vom Knoten aus verspricht. Der Algorithmus galt bis Anfang dieses Jahres als „ungeschlagen“ bei der Bewältigung dieser Aufgabe. Wer jedoch große Graphen behandelt, mit Hunderttausenden von Kanten, kämpft um jede Millisekunde. Für solche Fälle wurde im April 2025 ein neuer Algorithmus für die sogenannten Single-Source Shortest Paths (SSSP) veröffentlicht (siehe Deep Dive).
Über den Autor
Thure Dührsen studierte Informatik in Kiel mit den Schwerpunkten Theoretische Informatik und Mathematische Grundlagen. Berufliche Stationen führten ihn in die Erwachsenenbildung (u. a. zu Linux, Programmierung und Entwurf relationaler Datenbanken) sowie in den Bereich des Softwaretests. Der Schwerpunkt seiner Tätigkeit liegt heute im IT-Consulting, insbesondere in der Umsetzung von Projekten im Bereich der automatisierten Softwareverteilung, ergänzt durch Arbeiten in der technischen Redaktion.
