Der Dijkstra-Algorithmus findet nicht nur in der Informatik statt. Deshalb poste ich diesen Artikel hier und nicht in der Stacklounge.
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.
2. Der Algorithmus
Wie läuft der Algorithmus ab?
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
Das Beispiel kann ich hier leider nicht posten, da beim Upload Bilder automatisch in Text bzw. seltsames LaTeX-Code umgewandelt werden und sie dann (teilweise) verschwunden sind ...
Autor. Florian André Dalwigk
