Algorithmus von Dijkstra
Der Algorithmus von Dijkstra, benannt nach seinem Erfinder, Edsger Dijkstra, soll bei der Suche nach dem Abstand (d.h. einem kürzesten Pfad) zwischen zwei Knoten s und e in einem zusammenhängenden kantengewichteten Graphen G helfen.Tatsächlich lässt sich mit dem Algorithmus sogar der Abstand von einem Knoten s zu allen anderen Knoten des Graphenen berechnen. Dies ist dann äquivalent zum Algorithmus von Prim, der einen minimal spannenden Baum berechnet.
Eine andere Verallgemeinerung berechnet einen kürzesten A-B-Pfad, wobei A und B Mengen von Knoten im Graphen G sind.
Anschaulich lässt sich mit dem Algorithmus von Dijkstra eine kürzeste/billigste Route zwischen zwei Orten bestimmen. Der Algorithmus ist daher besonders wichtig für Routenplaner.
Der Algorithmus stützt sich auf das Optimalitätsprinzip, welches besagt, dass wenn der kürzeste Pfad von A nach C über B führt, der Teilpfad A B auch der kürzeste Pfad von A nach B sein muss.
Der Algorithmus setzt zuerst (je nach Ziel, siehe oben) X:={s} bzw. X:=A und erweitert dann iterativ die Knotenmenge X um einen im Graphen zu X am nächsten liegenden Knoten, bis (je nach Ziel, siehe oben) der Endknoten e, der letzte Knoten im Graphen oder ein Knoten aus B gefunden wurde. Ein am nächsten liegender Knoten ist dabei ein Knoten v aus V(G)\\X, zu dem eine Kante e={x,v} (in ungerichteten Graphen) bzw. e=(x,v) (in gerichteten Graphen) mit x aus X in G existiert, so dass für alle anderen Knoten w aus V(G)\\X gilt, dass jede Kante f={y,w} (in ungerichteten Graphen) bzw. f=(y,w) (in gerichteten Graphen) mit y aus X in G ein Kantengewicht besitzt, welches mindestens so groß ist, wie das der Kante e.
Das Grundprinzip des Algorithmus ist also sehr einfach. Die effiziente Bestimmung des nächsten Knotens ist aber aufwändig zu implementieren. Man benötigt als Datenstruktur so genannte Fibonacci-Heaps. Die Laufzeit beträgt: O(#Knoten + #Kanten * log(#Kanten)).
Im Unterschied zum Algorithmus von Prim bezieht sich der Dijkstra-Algorithmus bei der Berechnung eines minimal spannenden Baumes auf einen vorgegebenen Wurzelknoten, der bei Prim frei gewählt werden kann. Der berechnete spannende Baum ist aber in beiden Fällen minimal, wobei beim Algorithmus von Dijkstra aber ein spezieller minimal spannender Baum berechnet wird, der von allen Knoten kürzeste Pfade zum Wurzelknoten enthält.
Dijkstras Algorithmus wird im Internet als Routing Algorithmus in OSPF eingestetzt.
Weblinks