Dijkstra Algorithmus

Die “Schokofanten AG” hat ein neues Produkt entwickelt, um ihre Marktposition weiter auszubauen. Um das Produkt erfolgreich am Markt einzuführen und dem Fachpublikum vorzustellen, möchte der Geschäftsführer persönlich zur wichtigsten Schokoladenmesse des Landes in die Stadt E reisen.

Um seine Reiseroute zu planen, stellt er folgenden Graph auf, der die möglichen Reisewege und die Entfernungen der einzelnen Knotenpunkte zueinander darstellt:

Damit die kürzeste Route von Stadt A nach Stadt E gefunden werden kann, wird nun der Dijkstra Algorithmus angewendet:

1. Schritt: Initialisierung des Algorithmus

Um den Algorithmus zu initialisieren, wird eine Tabelle angelegt. Zu Beginn betragen die Kosten Null, da am Startpunkt begonnen wird. Der Weg zu den weiteren Knoten ist noch nicht bekannt, daher nehmen wir für die Kosten vorerst “unendlich” an.

In der Warteschlange befinden sich alle Knoten, die wir bereits gefunden haben. Zu Beginn ist das lediglich der Startpunkt A. Einen Vorgänger des Startpunktes gibt es nicht. Die gefüllte Tabelle sieht dann also folgendermaßen aus:

2. Schritt: 1. Iteration

Nach der Initialisierung des Algorithmus kann mit der ersten Iteration begonnen werden. In der Warteschlange aus dem vorherigen Schritt befindet sich der Knoten A. Daher wird dieser nun ausgewählt. Betrachtet werden dessen direkte Nachfolger, die Knoten B und D.

Die Entfernung von A nach B beträgt 100, die von A nach D 50. Diese stellen die Kosten dar. Da die beiden Nachfolger des Startpunktes nun betrachtet wurden, gilt dieser als erledigt. In der Warteschlange stehen nun B und D.

Mögliche Nachfolger der betrachteten Knoten sind C und E. Die Tabelle sieht dementsprechend folgendermaßen aus:

3. Schritt: 2. Iteration

Es folgt nun die 2. Iteration. Hierzu wird der Knoten aus der Warteschlange ausgewählt, welcher die geringsten Kosten aufweist, also Knoten D. Der Nachfolger dieses Knotens, Knoten E, wird nun betrachtet.

Die Kosten, um zum Knoten E zu gelangen, betragen 300. Da Knoten D nun betrachtet wurde, kann dieser aus der Warteschlange genommen und als erledigt markiert werden. Knoten B bleibt in der Warteschlange und wird um Knoten E ergänzt.

Die Tabelle gestaltet sich dann folgendermaßen:

4. Schritt: 3. Iteration

Auch bei der dritten Iteration wird nach dem gleichen Schema vorgegangen. Wir schauen uns nun die Kosten für den Knoten C an. Diese betragen 200. Sein direkter Vorgänger ist Knoten B. Wir können B damit als erledigt markieren und C zusätzlich in die Warteschlange aufnehmen.

Diese Informationen werden in der Tabelle ergänzt:

5. Schritt: 4. Iteration

Betrachten wir nun den Nachfolger von Knoten C. Dies ist Knoten E. Aktuell betragen die Kosten für E 300. Wenn wir aber den Weg über Knoten B und C wählen, betragen die neuen Kosten für E nur noch 250 mit dem neuen Vorgänger C. Damit ist auch Knoten E erledigt. Es gibt keine weiteren Nachfolger.

6. Schritt: 5. Iteration

In der letzten Iteration stellen wir fest, dass alle Knoten erledigt sind, da wir keinen Knoten mehr in die Warteschlange aufnehmen können. Wir können unseren Algorithmus an dieser Stelle also beenden.

Anhand der vollständigen Tabelle können wir nun den günstigsten Weg vom Startpunkt A zum Endpunkt E ablesen. Dazu betrachten wir die Tabelle rekursiv. Das bedeutet, wir starten die Betrachtung beim Knoten E. Dieser hat Gesamtkosten von 250. Sein Vorgänger ist Knoten C. Der Vorgänger von Knoten C ist Knoten B, welcher nach Knoten A folgt.

Der kürzeste Weg zum Knoten E ist also der Weg von A über B nach C zu E mit Gesamtkosten von 250.