Dijkstra-Algorithmus

Der Algorithmus von Dijkstra löst das Problem der kürzesten Wege für einen gegebenen Startknoten. Der Algorithmus berechnet einen kürzesten Weg zwischen dem gegebenen Startknoten und den anderen Knoten in einem kantengewichteten, gerichteten Graphen.

Der Dijkstra-Algorithmus gehört zu den Greedy Algorithmen der Graphentheorie.

Der Dijkstra-Algorithmus wurde im Jahr 1959 von dem niederländischen Informatiker Edsger Wybe Dijkstra (1930-2002) in seinem berühmten Artikel "A note on two problems in connexion with graphs" in der Zeitschrift Numerische Mathematik veröffentlicht.

Der Algorithmus

Gegeben sei ein Diagraph mit Knoten und einem Startknoten. Es werden alle kürzesten Wege zwischen dem Startknoten und allen anderen Knoten gesucht.

Die Vorgehensweise soll im Folgenden anhand eines Beispiels demonstriert werden.

Beispiel: Dijkstra-Algorithmus

Begonnen wird mit der Initialisierung:

Als Startknoten wird der Knoten 1 gewählt:

,

,

für die Knoten und

für alle Knoten .

Das Ganze wird in eine Tabelle eingetragen:

In der obigen Tabelle ist die Initialisierung eingetragen. Dabei wurde als Startknoten der Knoten 1 gewählt. Gekennzeichnet ist dies in der letzten Zeile mit einem . Dem Startknoten 1 wird zugeordnet, allen anderen Knoten . ist zunächst für alle Knoten leer. 

Es kann nun mit der 1. Iteration begonnen werden.

1. Iteration

1. Schritt: 

Zunächst wird ein Knoten ausgewählt, welcher sich in befindet und den kürzesten Weg aufweist. In befindet sich zunächst der Startknoten 1, also . 

2. Schritt: 

Es werden nun alle Nachfolger von Knoten 1 betrachtet. Die Nachfolger von Knoten 1 sind Knoten 2 und 3. 

Knoten 2:

Es wird dann der kürzeste Weg des Startknotens zur Pfeilbewertung des Nachfolgerknotens addiert:

. 

Das Ergebnis wird mit dem kürzesten Weg des Nachfolgerknotens verglichen:

.

Ist das Ergebnis (hier: 120) kleiner als der kürzeste Weg des Nachfolgerknotens (hier: ) so wird der kürzeste Weg des Nachfolgerknotens gleich dem Ergebnis gesetzt.

Es gilt also und demnach wird gesetzt. Der Vorgänger von Knoten ist demnach Knoten :

.

Knoten 3:

Für den Knoten 3 gilt dieselbe Vorgehensweise:

.

.

3. Schritt: 

Der Knoten 1 welcher sich in befindet wird entfernt und bei der weiteren Betrachtung nicht weiter berücksichtigt.

Die neue Tabelle ergibt sich zu:

2. Iteration

1. Schritt: 

Zunächst wird ein Knoten ausgewählt, welcher sich in befindet und den kürzesten Weg aufweist. In befinden sich die Knoten 1 und 2. Den kürzesten Weg besitzt Knoten 3 mit . Dieser wird ausgewählt.

2. Schritt: .

Es werden nun alle Nachfolger von Knoten 3 betrachtet. Die Nachfolger von Knoten 1 sind Knoten 4 und 5. 

Knoten 4:

.

.

Knoten 5: 

.

.

3. Schritt: 

Der Knoten 3 welcher sich in befindet wird entfernt und bei der weiteren Betrachtung nicht weiter berücksichtigt.

3. Iteration

1. Schritt: 

Zunächst wird ein Knoten ausgewählt, welcher sich in befindet und den kürzesten Weg aufweist. In befinden sich die Knoten 2, 4 und 5. Den kürzesten Weg besitzt Knoten 5 mit . Dieser wird ausgewählt.

2. Schritt: 

Es werden nun alle Nachfolger von Knoten 5 betrachtet. Die Nachfolger von Knoten 5 sind Knoten 4 und 6. 

Knoten 4:

.

.

Knoten 6: 

.

.

3. Schritt: 

Der Knoten 5 welcher sich in befindet wird entfernt und bei der weiteren Betrachtung nicht weiter berücksichtigt.

4. - 6. Iteration

Es wird Knoten mit den Nachfolgern 2 und 6 gewählt. Die kürzesten Wege der Nachfolgerknoten werden nicht verändert, da:

: . Der Vorgänger bleibt Knoten .

: . Der Vorgänger bleibt Knoten .

Der Knoten wird aus entfernt. 

Es wird der Knoten mit den Nachfolgerknoten 4 gewählt. Der kürzeste Weg von Knoten 4 wird nicht verändert:

: . Der Vorgänger bleibt Knoten .

Der Knoten 6 wird aus entfernt. 

Es wird der Knoten mit den Nachfolgerknoten gewählt. Der kürzeste Weg von Knoten wird nicht verändert:

: . Der Vorgänger bleibt Knoten .

Der Knoten 2 wird aus entfernt. 

Es kann nun der kürzeste Weg vom Startknoten aus zu den einzelnen Knoten aus der Tabelle abgelesen werden. Wird zum Beispiel der Weg zum Knoten 4 gesucht, so muss man die Tabelle rückwärts lesen:

Der Knoten 4 hat als Vorgänger Knoten 5, dieser hat als Vorgänger Knoten 3 und dieser hat als Vorgänger Knoten 1.