In diesem Kurs lernst du den Dijkstra-Algorithmus und eine mögliche Anwendung davon kennen: Finde effiziente Wege durch ein Straßennetz mit dem Dijkstra-Algorithmus!

Benötigtes Vorwissen:

• Graphen (Begriff Knoten, Kante, Kantengewicht)

Bearbeitungszeit:

ca 30 Min

Um den Weihnachtsmann zu entlasten, bekommt der Wichtel Dijkstra Jr. die Aufgabe, die Dörfer rund um die Werkstatt am Nordpol mit Geschenken zu beliefern.

Die Knoten des Graphen stehen auf dieser Karte für die einzelnen Dörfer, die Zahlen an den Kanten sind die Längen der (in der Realität natürlich nicht so geraden) Straßen in Kilometern.

Dijkstra Jr. hat ein paar Freunde versammelt, die ihn unterstützen sollen und macht sich mit ihnen an die Routenplanung.

Sein Ziel: Für jedes Gebiet in der Nachbarschaft möchte er den kürzesten Weg von der Weihnachtswerkstatt dorthin finden, um so effiziente Routen zu planen.

Überlegung: Bevor du einen Algorithmus kennenlernst, der dieses Problem auch für sehr große Graphen lösen kann, kannst du für dieses einfache Beispiel selbst eine Lösung finden. Notiere dir für jedes Dorf im Graphen den kürzesten Weg von der Werkstatt zu diesem Ort.

Vorbereitung

Schreibe in eine Tabelle alle Knoten des Graphen (alle Städte) und lege als Startdistanz für alle Städte außer für den Ausgangspunkt den Wert unendlich $\left(\mathrm{\infty }\right)\backslash left(\backslash infty\backslash right)$ fest.

Zunächst kannst du für jeden Ort, der direkt mit der Werkstatt verbunden ist, die Distanz von $\mathrm{\infty }\backslash infty$⁣, auf die angegebenen km senken und diesen Ort als abgehandelt markieren. In diesem ersten Schritt sind alle Distanzen automatisch kürzer als die zuerst festgelegte und du musst deshalb nichts nachrechnen oder überprüfen.

Anschließend suchst du unter den gerade markierten Orten das Dorf heraus, das die kürzeste Distanz zum Startknoten (also der Werkstatt) hat und noch nicht besucht wurde. Dieser Ort ist Schlittenstadt. Markiere ihn als neuen aktuellen Knoten (rot umrandet in Grafik, fett in Tabelle).

Wähle aus der Tabelle den Ort aus, der die kleinste Distanz zum Startort hat und noch nicht untersucht wurde. Dieser Ort ist Winterweiher. Markiere ihn als aktuellen Ort:

Wähle aus der Tabelle den Ort aus, der die kleinste Distanz zum Startort hat und noch nicht untersucht wurde. Dieser Ort ist Kugelkaff. Markiere ihn als aktuellen Ort:

Jetzt hast du zwar zu jedem Dorf einen Weg gefunden, dieser muss aber nicht der kürzeste sein! Du musst alle Knoten einmal untersucht haben, damit der Dijkstra-Algorithmus das gesuchte Ergebnis liefert.

Wähle deshalb erneut aus der Tabelle den Ort aus, der die kleinste Distanz zum Startort hat und noch nicht untersucht wurde. Dieser Ort ist Plätzchen-Port. Markiere ihn als aktuellen Ort:

Auch Dominodorf muss noch untersucht werden. Allerdings verändern sich die Wege dadurch nicht: Nach Kugelkaff wären es 20 km, nach Plätzchen-Port 17 km.

Die finalen Distanzen zwischen der Werkstatt und allen Städten sehen also wie folgt aus:

Beachtet man die Vorgänger, ergeben sich daraus folgende Routen:

Beim Vorgehen von Dijkstra Jr. handelt es sich um einen Algorithmus. Das heißt, er lässt sich zum Beispiel mithilfe eines Struktogramms übersichtlich beschreiben und darstellen. Alle Handlungen, die du in den letzten Schritten mit den Wichteln durchgeführt hast, lassen sich "formal" so aufschreiben: