Der Algorithmus von Dijkstra

Edsger W. Dijkstra hat 1956 – nach eigener Aussage in zwanzig Minuten beim Kaffee in einem Café – ein Verfahren erdacht, das kürzeste Wege findet, ohne alle Wege auszuprobieren. Es macht genau, was das Wasser tut.

So geht der Algorithmus von Dijkstra

Der Start bekommt den Abstand 0, alle anderen Knoten den vorläufigen Abstand ∞ („noch unbekannt“).
Lege unter den noch nicht festgelegten Knoten den mit dem kleinsten vorläufigen Abstand fest. Sein Abstand ist jetzt endgültig.
Schaue dir die noch nicht festgelegten Nachbarn dieses Knotens an: Abstand des festgelegten Knotens + Kantengewicht. Ist das kleiner als der bisherige Wert, streiche den alten Wert durch und schreibe den neuen daneben.
Wiederhole ab Schritt 2, bis alle Knoten festgelegt sind.

Ein Beispiel – Schritt für Schritt

Gesucht sind die kürzesten Abstände von A zu allen Knoten. Die Zahlen an den Knoten sind die vorläufigen Abstände; wird ein Wert durch einen kleineren ersetzt, wird er durchgestrichen. Starte den Film mit ▶ oder gehe mit ⏮ und ⏭ Schritt für Schritt. Grün sind die festgelegten Knoten, orange der Knoten, dessen Nachbarn gerade geprüft werden.

Im Werkzeug der Aufgaben klickst du einen Knoten an, um ihn festzulegen, und trägst dann die neuen Werte der Nachbarn ein. Die Zahlen über den Knoten sind die vorläufigen Abstände.

Dijkstra mit Anleitung

Aufgabe 1: Bestimme mit dem Algorithmus von Dijkstra die kürzesten Abstände von A zu allen Knoten. Für die ersten beiden Knoten zeigt dir die Anleitung genau, was zu tun ist; danach machst du allein weiter.

Dijkstra Schritt für Schritt

Aufgabe 2: Bestimme mit dem Algorithmus von Dijkstra die kürzesten Abstände von A zu allen Knoten.

Berufsverkehr

Morgens pendeln viele Menschen aus dem Umland zur Arbeit nach Saarbrücken, nach Feierabend fahren sie wieder zurück. Dann sind vor allem die Straßen in die Stadt hinein (morgens) bzw. aus der Stadt heraus (abends) voll. Ein Navi rechnet deshalb nicht mit festen Fahrzeiten, sondern mit den Zeiten, die gerade gelten.

Die rechte Karte zeigt die Fahrzeiten an einem Werktag gegen 7:30 Uhr für die Fahrt Richtung Saarbrücken (gerundet, vereinfacht).

ohne Verkehr

morgens Richtung Saarbrücken

S = Saarlouis, D = Dillingen, L = Lebach, W = Schwalbach, V = Völklingen, P = Püttlingen, R = Riegelsberg, H = Heusweiler, B = Saarbrücken

Dijkstra im Berufsverkehr

Aufgabe 3: Bestimme mit dem Algorithmus von Dijkstra die schnellsten Fahrzeiten am Morgen von Saarlouis (S) zu allen Orten.

Freitext

Aufgabe 4: Dijkstra liefert zunächst nur die Fahrzeiten. Wie kann man sich zusätzlich merken, auf welchem Weg man nach Saarbrücken kommt?

💡 Zum Speichern deiner Antwort bitte einloggen.

Multiple Choice

Aufgabe 6: Warum muss Dijkstra nicht alle Wege ausprobieren?

Weil der Abstand eines festgelegten Knotens endgültig ist – Umwege dorthin muss man nie mehr betrachten. Weil er zufällig rät und meistens Glück hat. Weil er immer die kürzeste Kante des ganzen Graphen nimmt. Weil er nur die Kanten am Start betrachtet.

✏️ Übungen zu diesem Kapitel

4 freiwillige Aufgaben zum Üben und Weiterdenken.

Zu den Übungen →