• Artikel
• Bearbeiten
• Historie
• Druckansicht

Dijkstra

Der Dijkstra Algorithmus dient der Berechnung eines kürzesten Pfades zwischen einem Startknoten und einem beliebigen Knoten in einem kantengewichteten Graphen.

Die Gewichte dürfen dabei nicht negativ sein. Für Graphen mit negativen Gewichten ist der Bellman-Ford-Algorithmus geeignet.

Beispiel

Betrachten Sie das Beispiel rechts Suche den Weg von "A nach E"

A	B	C	D	E
0					-	{}
0	2	7			-	{A}
0	2	7	13	15	-	{A,B}
0	2	7	10	9	-	{A,B,C}
0	2	7	10	9	-	{A,B,C,E}
0	2	7	10	9	-	{A,B,C,E,D}

Ergebnis: Der kürzeste Weg ist [AC],[CE] mit dem Gewicht 9

Algorithmus

G bezeichnet den gewichteten Graphen mit V (engl. vertex) als Knotenmenge, E (engl. edge) als Kantenmenge und w als Gewichtsfunktion, welche Kanten auf positive reelle Zahlen abbildet. Der Knoten s ist der Startknoten, Q ist die Prioritätswarteschlange der noch zu bearbeitenden Knoten und g ist ggf. ein spezieller Zielknoten, bei dem abgebrochen werden kann, wenn seine Distanz zum Startknoten bekannt ist.

Nach Ende des Algorithmus enthält d[v] die Abstände aller Knoten v zu s. In π[v] ist ein spannender Baum der von s aus ausgehenden minimalen Wege in Form eines In-Tree gespeichert.

Wird bei Erreichen von g abgebrochen, so enthalten d[v] und π[v] diese Werte nur für alle zuvor betrachteten Knoten v. Das sind mindestens die, die kleineren Abstand als g zu s besitzen.

Weblinks

• Dijkstra Java Applet