Rechnernetze

Dijkstras Shortest-Path-Algorithmus

Vorgegeben sei ein Rechnernetz in Form eines gewichteten, ungerichteten Graphen, wobei die Gewichtungsfunktion die Distanz zwischen zwei Knoten repräsentiert. Gesucht ist der kürzeste Weg zwischen den Knoten 1 und 6.

Der Algorithmus sucht zunächst den Knoten mit dem kürzesten Abstand zum Quellknoten, markiert diesen als permanent und sucht dann unter den verbleibenden Knoten denjenigen mit dem kürzesten Abstand zum Quellknoten usw. Um den Knoten mit dem kürzesten Abstand zu finden, werden nur die Knoten betrachtet, die mit einem Schritt vom Quellknoten oder von einem der als permanent markierten Knoten erreicht werden können. Da jeder andere Knoten nur über einen der betrachteten Knoten erreicht werden kann, ist der mit dem kürzesten Abstand zum Quellknoten in dieser Menge zu finden, so dass der Suchraum auf die direkten Nachbarknoten eingeschränkt werden kann. Ist das Netz nicht stark vermascht, so lässt sich mit linearem Aufwand für einen Quellknoten der kürzeste Weg zu allen anderen Knoten des Netzes finden.

Der erste Schritt des Algorithmus besteht darin, alle Knoten des Graphen mit einer initialen Marke (s, d) zu versehen. Der erste Wert der Marke weist einen Knoten als direkten Nachfolger des Knotens s aus und ordnet ihm einen Abstand d zu. In der Initialisierungsphase werden jedoch zunächst alle Knoten mit s = –1 und mit dem Abstandswert ' markiert. Eine Ausnahme bildet lediglich der Quellknoten, der als permanent markiert wird, d.h. die Werte der Marken werden nicht mehr verändert, und für dessen Abstand (nämlich zu sich selbst) wird null eingetragen.

Im zweiten Schritt werden dann alle direkten Nachbarknoten des als permanent gekennzeichneten Knotens untersucht und mit der Nummer des Quellknotens sowie mit dem Abstand zu diesem beschriftet: (Nummer des Quellknotens, Abstand zum Quellknoten). Der Nachbarknoten mit dem kleinsten Abstandswert (im Beispiel Knoten 4) wird zum Arbeitsknoten. Falls mehrere Nachbarknoten den gleichen minimalen Abstand aufweisen, kann die Auswahl zufällig erfolgen. Der Weg zwischen dem Quell- und dem Arbeitsknoten wird als permanent markiert, da es keine kürzere Verbindung zwischen diesen beiden Knoten geben kann; im Bild sind permanente Knoten fett markiert:

Im allen weiteren Schritten werden alle Nachbarknoten des aktuellen Arbeitsknotens untersucht und beschriftet; trifft man dabei auf einen bereits markierten, nicht permanenten Knoten, so wird die Marke geändert, falls ein kleinerer Gesamtabstand zum Quellknoten gefunden wird; andernfalls bleibt die Marke unverändert. Dann werden alle beschrifteten, nicht permanenten Knoten nach dem kleinsten Abstand zum Quellknoten durchsucht; der Knoten mit den kleinsten Abstand wird als permanent markiert und zum neuen aktuellen Arbeitsknoten (Knoten 5 im Beispiel):

Dieser Schritt wird solange wiederholt, bis alle Knoten als permanent markiert sind:

ß

ß