Algorithmus von Dijkstra

Der Algorithmus von Dijkstra (nach seinem Erfinder Edsger Dijkstra), dient der Berechnung eines kürzesten Pfades zwischen zwei Knoten s und e in einem zusammenhängenden kantengewichteten Graphen G.

Anwendungen

Routenplaner sind ein prominentes Beispiel, bei der dieser Algorithmus eingesetzt werden kann. Der Graph repräsentiert hier das Straßennetz, welches verschiedene Punkte miteinander verbindet. Gesucht ist die kürzeste Route zwischen zwei Punkten.

Dijkstras Algorithmus wird auch im Internet als Routing-Algorithmus in OSPF eingesetzt.

Implementation

• Setzte i = 0;
• Setze s als Startgraph T und nummeriere s mit i (= 0);
• Solange T noch nicht e enthält,
• • Erhöhe i um 1;
  • suche eine Kante minimalen Gewichts, die einen Knoten, der nicht in T ist, mit T verbindet und
  • füge diese Kante und den damit verbundenen Knoten v zu T hinzu;
  • Nummeriere v mit i;
• Laufe von e beginnend zurück zu s, indem als nächster Knoten immer der Knoten mit kleinster Nummerierung gewählt wird;

Der im letzten Schritt durchlaufene Pfad, stellt einen kürzesten Pfad zwischen e und s dar.

Berechnung des Abstandes

Will man den Abstand der Knoten s und e berechnen, so braucht man beim Zurücklaufen im letzten Schritt einfach nur die Kantengewichte der entlanggelaufenen Kanten zu addieren.

Verallgemeinerung

Wählt man eine ganze Menge S von Knoten als Startknoten und einen ganze Menge E von Knoten als Endknoten, so berechnet der Algorithmus von Dijkstra einen kürzesten Pfad, der einen Knoten aus S mit einem Knoten aus E verbindet. Der Algorithmus muss dann so abgewandelt werden, dass zu Beginn alle Startknoten in T aufgenommen und mit 0 nummeriert werden und die Schleife abgebrochen wird, sobald ein Knoten aus E erreicht, also in T eingefügt wurde.

Ändert man die Abbruchbedingung dahin, dass erst nach erreichen aller Knoten die Schleife verlassen wird, so berechnet der Algorithmus einen minimal spannenden Baum in G, mit der Eigenschaft, dass schnell von allen Knoten die kürzesten Pfade zum Startknoten s gefunden werden können (in dem man den letzten Schritt für den Knoten ausführt).

Vergleich mit Prim

Der Algorithmus von Dijkstra ähnelt dem Algorithmus von Prim. Letzterer dient der Berechnung eines minimal spannenden Baumes. Statt s kann Prim den Startknoten beliebig wählen. Die Schleife wird abgebrochen, wenn alle Knoten erreicht wurden. Da es nur auf die Berechnung eines minimal spannenden Baumes ankommt, und nicht auf die kürzesten Pfade zu s, ist einen Nummerierung der Knoten bei Prim nicht notwendig. Ansonsten sind die Algorithmen von Dijkstra und Prim identisch.

Optimalitätsprinzip

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.

Effiziente Implementierung

Das Grundprinzip des Algorithmus ist relativ 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(m + n * log(n)), wobei m die Zahl der Kanten und n die Zahl der Knoten ist.

Siehe auch: Floyd-Warshall-Algorithmus, Bellman-Ford-Algorithmus

Weblinks

• Ein anschauliches Beispiel kann hier gefunden werden.