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 spanennden Baum berechnet.

Eine andere Verallgemeinerung berechnet einen kürzesten A-B-Pfad, wobei A und B Mengen von Knoten im Graphen sind.

Anschaulich läßt 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ähesten liegenden Knoten, bis ein Knoten aus B bzw. der Endknoten e gefunden wurde.

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