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 in einem zusammenhängenden kantengewichteten Graphen helfen.

Tatsächlich lässt sich mit dem Algorithmus sogar den 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.

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.

Ausgehend von s werden die kürzesten Wege für die Knoten mit aufsteigendem Abstand nacheinander bestimmt. Zuerst wird aus den Knoten, die mit s durch eine Kante verbunden sind, der Knoten v mit dem kürzesten Abstand zu s ausgewählt. Aus den gewählten Knoten (hier s und v) werden die so genannten Randknoten bestimmt. Dies sind Knoten zu denen es einen Weg nach s über die gewählten Knoten gibt. D.h. von einem Randknoten gibt es eine Kante zu einem gewählten Knoten. Durch Neubestimmung der Randknoten ist es dann möglich, iterativ so fortzufahren, bis für jeden Knoten (oder dem Endknoten) ein kürzester Weg ausgehend von s gefunden wurde.

Der vorangegangene Abschnitt sollte etwas genauer und formaler werden.

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