Dijkstra-Algorithmus

Der Dijkstra-Algorithmus oder auch Algorithmus von Dijkstra ist ein Algorithmus der nach seinem Erfinder Edsger Wybe Dijkstra benannt wurde und die kürzeste Pfade für einen gegebenen Startknoten bestimmen soll. Bei der Knotenwahl für den kürzesten Weg verfolgt der Algorithmus dabei eine sogenannte Greedy-Strategie. Dabei fällt die Wahl immer auf den Knoten, der die geringste Entfernung zum Startknoten besitzt. Damit müssen beim Dijkstra-Algorithmus alle Kantengewichtungen nichtnegativ sein!

Dijkstra-Algorithmus Beispiel

Die Funktionsweise des Dijkstra-Algorithmus macht man sich am besten an einem konkreten Beispiel klar. Gegeben sei folgender gerichtete Graph:

Beispiel Graph für Dijkstra-Algorithmus

Wie man sieht existieren 5 Knoten, wobei der Startknoten für den Dijkstra-Algorithmus Knoten a sei. Nun durchläuft der Algorithmus zum Start erst einmal eine Initialisierung. Dabei markiert der Knoten sich selbst, setzt die Distanz zu sich selbst auf 0 und die Distanz zu allen anderen Knoten auf Unendlich. Es ergibt sich folgende Tabelle:

Initialisierung des Dijkstra-Algorithmus

Nun beginnt die erste Iteration, also der erste Durchlauf und damit die eigentliche Arbeit des Algorithmus. Der Dijkstra-Algorithmus markiert alle benachbarten Knoten und nimmt sie in seine Tabelle mit den Entfernungsangaben auf. In diesem Fall werden die Knoten b und d markiert und ihre Entfernungen aufgenommen. Es gibt sich nachfolgende Tabelle, sowie noch einmal die grafische Ansicht, wobei die markierten Knoten rot sind.

Tabelle der ersten Iteration des Dijkstra-Algorithmus 1. Iteration des Dijkstra-Algorithmus

Für die zweite Iteration wird nun der Knoten ausgewählt, der in den markierten Knoten die geringste Distanz aufweist. In diesem Beispiel sind der Knoten b mit der Distanz 10 und der Knoten d mit der Distanz 80 markiert. Da 10<80 ist, betrachtet man in der zweiten Iteration nun also Knoten b. Auch in dieser Iteration kommen wieder Entfernungen von Knoten hinzu, nämlich die Nachbarn von b. Dies wäre e und c, die von Startknoten a über Knoten b nun erreichbar sind. Bei den Entfernungen für die Tabelle muss man nun darauf achten, dass man nicht nur die Entfernung von b zu seinem Nachbarn aufnimmt, sondern zu dieser Entfernung auch noch die Entfernung von a zu b aufsummiert. So ergibt sich für die Entfernung von Knoten e zu a 10+20 = 30. Es ergibt sich nachfolgende Tabelle mit dem zugehörigen Schaubild. Darin ist nun der gerade zu betrachtende Knoten, also Knoten b, gelb eingezeichnet. Neben Knoten d, gesellen sich nun noch Knoten e und c zu den markierten Knoten (rot eingezeichnet).

Tabelle der zweiten Iteration des Dijkstra-Algorithmus 2. Iteration des Dijkstra-Algorithmus

Auch in der dritten Iteration wird wieder der Knoten in den markierten Knoten ausgewählt, der die geringsten Distanz aufweist, also Knoten e, da 30<60<80 ist. Es kommt in dieser Iteration nun zwar kein neuer Knoten dazu, da Startknoten a inzwischen alle Knoten im Graphen erreichen kann, dafür ändert sich aber nun zwei Strecken. Von Knoten e ist nämlich Knoten d und c ebenfalls für a zu erreichen. Der Algorithmus errechnet also die Distanz über Knoten e und vergleicht den Wert mit dem Wert der schon in der Tabelle steht. Und siehe da, Knoten d und Knoten c ist über Knoten e jeweils günstiger zu erreichen. Es muss also die Tabelle mit den neuen Entfernungen aktualisiert werden und der Vorgänger mit Knoten e ersetzt werden. Es ergibt sich damit nachfolgende Tabelle und das entsprechende Schaubild.

Tabelle der dritten Iteration des Dijkstra-Algorithmus 3. Iteration des Dijkstra-Algorithmus

Anschließend folgt die vierte Iteration, hier gibt es aber keinen neuen Knoten und keine Änderung.

Tabelle der vierten Iteration des Dijkstra-Algorithmus 3. Iteration des Dijkstra-Algorithmus

Und auch in der fünften Iteration bleibt alles beim alten.

Tabelle der fünften Iteration des Dijkstra-Algorithmus 5. Iteration des Dijkstra-Algorithmus

Wie man nun sieht, ist die Menge der markierten Knoten nach der fünften Iteration leer. Dies ist das Zeichen für den Algorithmus zu stoppen. Die kürzesten Wege für den Startknoten wurden gefunden. Es ergibt sich folgendes Bild:

Abschluss des Dijkstra-Algorithmus
Anmerkung: Die Schaubilder stammen aus dem wirklich empfehlenswerten Dijkstra's Shortest Path Algorithm Applet von Carla Laffra von der Pace University. Im Applet kann man sich eigene Graphen schnell zusammenklicken und darüber dann den Dijkstra-Algorithmus laufen lassen. Ideal noch einmal für das eigene Verständnis und kleinere Experimente, wie sich der Dijkstra-Algorithmus in bestimmten Situationen verhält.