· 

Der Dijkstra-Algorithmus

1. Einführung

Woher weiß ein Paket, welchen Weg es durch ein Netzwerk nehmen muss, um von einem Router S zu einem Router Z zu gelangen? Ganz einfach! Durch ein Routing-Protokoll, das einen Algorithmus nutzt, mit dem man den kürzesten Weg von einem bestimmten Router zu allen anderen Routern im Netzwerk berechnen kann. Der Algorithmus, mit dem man das bewerkstelligen kann, heißt Dijkstra-Algorithmus. Das Link-State-Routing-Protokoll Open Shortes Path First (OSPF) nutzt diesen Algorithmus, mit dem das Wissen über die Kosten zum Erreichen von Routern innerhalb des Netzwerks aufgebaut werden kann.

Als Basis wird ein Netzwerk betrachtet, das aus verschiedenen Knotenpunkten (Routern) besteht, die über Links miteinander verbunden sind. An diesen Links sind  "Kosten" eingetragen. Damit ist der Aufwand gemeint, mit dem man von einem Knoten (Router) zu einem anderen Knoten (Router) kommen kann. Diese Quantifizierung nennt man auch Metrik. Wenn es beim Routing nur um die Anzahl der Hops geht (d. h. wie viele Router muss man durchlaufen, bis man am Ziel angekommen ist), dann entsprechen die Kosten an jedem Link 1.

Anstelle des technischen Begriffs "Router" verwenden wir fortan "Knoten", da der Algorithmus auch in anderen Bereichen als dem Routing angewendet wird.


2. Der Algorithmus

Wie läuft der Algorithmus ab?

Algorithmus: Dijkstra-Algorithmus

Eingabe: Gewichteter Graph (Netzwerk), Startknoten \(S\)
Ausgabe: Kürzeste Wege von \(S\) zu allen Knoten
  1. Initialisierung:
    • Erstelle eine Liste mit allen unbesuchten Knoten.
    • Setze die Kosten zum Erreichen des Startknotens auf \(0\).
    • Setze die Kosten aller anderen Knoten auf \(\infty\).
  2. Setze den Knoten mit den geringsten Kosten als aktuell besuchten Knoten. Wenn es keinen Knoten mit geringsten Kosten gibt (z. B. weil zwei Knoten mit denselben Kosten erreicht werden können), wähle zufällig einen aus.
  3. Berechne von dem aktuell besuchten Knoten aus Schritt 2 die Kosten zu seinen direkten Nachbarn durch Addition der eigenen Kosten zu den Kosten entlang der Kante (bzw. des Wegs) zu dem entsprechenden Nachbarn.
  4. Wenn die in Schritt 3 entstandenen Kosten geringer sind als die aktuellen Kosten zum Erreichen des Nachbarn, dann ersetze diese durch die geringeren Kosten und setze den aktuell besuchten Knoten als dessen Vorgänger. Ansonsten mache mit dem nächsten Schritt weiter.
  5. Wurden alle Knoten besucht? Falls nein, mache bei Schritt 2 weiter. Falls ja, endet der Algorithmus.

3. Beispiel

Um den bislang nur theoretisch betrachteten Algorithmus mit Leben zu füllen, betrachten wir das folgende Netzwerk:

Von dem Router S aus sollen die kürzesten Wege zu allen anderen Routern berechnet werden. Das Ergebnis wird in einer Tabelle gespeichert. Für diese gibt es verschiedene Darstellungsmöglichkeiten, die du für gewöhnlich am Anfang deiner Vorlesung gezeigt bekommst. In unserer Tabelle finden sich nur die einzelnen Knoten-Namen, die Kosten zum Erreichen dieses Knotens und der direkte Vorgänger, über den dieser Knoten erreicht wird, wieder. 

Bei der Initialisierung weisen wir dem Knoten S die Kosten 0 und allen weiteren Knoten die Kosten ∞ zu. Zudem definieren wir eine Liste mit allen bereits besuchten Knoten, die zu Beginn leer ist. 

Wir beginnen nun bei dem Startknoten S. Von dort aus können wir die Knoten A und D erreichen. Die Kosten von S sind 0. Wir erreichen A also, indem wir 0+20 rechnen. Da 20 kleiner als unendlich ist, ersetzen wir ∞ durch die neu berechneten Kosten und legen S als den Vorgänger von A fest. 

Wir erreichen D, indem wir von S aus 0+10 rechnen. Da 10 kleiner als ∞ ist, ersetzen wir ∞ durch die neu berechneten Kosten und legen S als den Vorgänger von D fest.

Jetzt kommt S in die Liste der bereits besuchten Knoten. Wurden alle Knoten bereits besucht? Nein! Deshalb machen wir mit dem bislang unbesuchten Knoten weiter, der die geringsten Kosten hat. Das ist in diesem Fall Knoten D. Von dort aus erreichen wir die Knoten S, A und C.

Da S bereits besucht wurde, ignorieren wir diesen Knoten. A erreichen wir von D aus mit den Kosten 10+20=30. Da 30 nicht kleiner als 20 ist, wird keine Änderung vorgenommen. C erreichen wir von D aus mit den Kosten 10+50=60. Da 60 kleiner als ∞ ist, ersetzen wir ∞ durch die neu berechneten Kosten und legen D als den Vorgänger von C fest.

Jetzt kommt D in die Liste der Knoten, die bereits besucht wurden. Wurden alle Knoten bereits besucht? Nein! Deshalb wir machen wir mit dem bislang unbesuchten Knoten weiter, der die geringsten Kosten hat. Das ist in diesem Fall Knoten A.

Von A aus erreichen wir die Knoten S, D, C und B. S und D können wir ignorieren, da diese bereits besucht wurden. Von A aus erreichen wir den Knoten C mit den Kosten 20+50=70. Da 70 größer als 60 ist, wird keine Änderung vorgenommen. Der Knoten B kann mit den Kosten 20+20=40 erreicht werden. Da 40 kleiner als ∞ ist, ersetzen wir  ∞ durch die neu berechneten Kosten und legen A als den Vorgänger von B fest.

Jetzt kommt A in die Liste der Knoten, die bereits besucht wurden. Wurden alle Knoten bereits besucht? Nein! Deshalb wir machen wir mit dem bislang unbesuchten Knoten weiter, der die geringsten Kosten hat. Das ist in diesem Fall Knoten B.

Von B aus erreichen wir die Knoten A und C. A können wir ignorieren, da dieser bereits besucht wurde. Von B aus erreichen wir den Knoten C mit den Kosten 40+10=50. Da 50 kleiner als 60 ist, ersetzen wir die Kosten von C durch die neu berechneten Kosten und legen B als den Vorgänger von C fest. 

Jetzt kommt B in die Liste der Knoten, die bereits besucht wurden. Nun ist noch ein Knoten unbesucht, nämlich C.

Von ihm aus erreichen wir nur bereits besuchte Knoten und es kann auch keine weitere Kostenreduktion erfolgen, d. h. der Algorithmus terminiert an dieser Stelle.


4. Weg zu einem Knoten angeben

Wenn du mit der Ergebnistabelle nun den kürzesten Weg von dem Startknoten zu einem bestimmten Endknoten berechnen willst, liest du diesen rückwärts aus der Tabelle ab. Wie funktioniert das? Nehmen wir an, du möchtest von Knoten S zu Knoten C. Du schaust zunächst in der Tabelle nach, wo sich Knoten C befindet. Du liest dessen Vorgänger (das ist B) ab und schreibst ihn vor das C. Nun liest du den Vorgänger von B (das ist A) ab und schreibst auch diesen vor das B. Als letztes liest du noch den Vorgänger von A ab und erhältst den Startknoten. Der kürzeste Weg von S nach C lautet also S->A->B->C.