Algorithmus von Dijkstra

Tatsächlich lässt sich mit dem Algorithmus der Abstand von einem Knoten s zu allen anderen Knoten des Graphen 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 Dijkstra eine kürzeste/billigste Route zwischen zwei Orten Der Algorithmus ist daher besonders wichtig für Routenplaner .

Der Algorithmus setzt zuerst (je nach 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 Ziel siehe oben) der Endknoten e der letzte Knoten im Graphen oder Knoten aus B gefunden wurde. Ein am nächsten liegender 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 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 das der Kante e .

Das Grundprinzip des Algorithmus ist also einfach. Die effiziente Bestimmung des nächsten Knotens aber aufwändig zu implementieren. Man benötigt als so genannte Fibonacci-Heaps .

Im Unterschied zum Algorithmus von Prim bezieht sich der Dijkstra-Algorithmus bei der eines minimal spannenden Baumes auf einen vorgegebenen der bei Prim frei gewählt werden kann. berechnete spannende Baum ist aber in beiden minimal wobei beim Algorithmus von Dijkstra aber spezieller minimal spannender Baum berechnet wird der allen Knoten kürzeste Pfade zum Wurzelknoten enthält.

Weblinks

• Ein anschauliches Beispiel kann hier gefunden werden.

Bücher zum Thema Algorithmus von Dijkstra

Dieser Artikel von Wikipedia unterliegt der GNU FDL.