Dijkstra-Algorithmus

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 helfen.

Tatsächlich lässt sich mit dem Algorithmus sogar 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 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 setzt zuerst X:=A bzw. X:={s} und erweitert dann iterativ die Knotenmenge X um den im Graphen zu X am nächsten liegenden Knoten, bis (je nach Ziel, s.o) der Endknoten e, der letzte Knoten im Graphen oder ein Knoten aus B gefunden wurde.

Das Grundprinzip des Algorithmus ist also sehr einfach. Die effiziente Bestimmung des nächsten Knotens ist aber aufwendig zu implementieren. Man benötigt als Datenstruktur sogenannte Fibonacci-Heaps.