Kursangebot | Operations Research 1 | Dijkstra-Algorithmus

Operations Research 1

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.

Merke

Greedy-Algorithmen zeichnen sich dadurch aus, dass sie schrittweise denjengen Folgezustand auswählen, der zum Zeitpunkt der Wahl das beste Ergebnis verspricht.

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 $n$ Knoten und einem Startknoten. Es werden alle kürzesten Wege zwischen dem Startknoten und allen anderen Knoten gesucht.

Methode

Algorithmus von Dijkstra

Gegeben sei ein Diagraph mit $n$ Knoten und einem Startknoten $a$. Alle Pfeile seien mit $k(i,j)$ bewertet. Gesucht wird der kürzeste Weg zwischen dem Startknoten und allen anderen Knoten des Diagraphen.

Sei $D(i)$ die kürzeste Entfernung vom Startknoten $a$ zum Knoten $i$, $V(i)$ der unmittelbare Vorgänger von Knoten $i$ auf dem kürzesten Weg vom Startknoten $a$ zum Knoten $i$ und die Menge $M$ die Menge einer bestimmten Auswahl von Knoten.

Initialisierung:

$M = \{a \}$

$D(a) = 0$ und $D(i) = \infty$ für alle Knoten $i \neq a$.

$V(i) = - $ für alle Knoten $i$.

Iteration:

1. Schritt: Auswahl eines Knotens $K \in M$ mit $D(K) = min \{D(i) | i \in M \}$.

2. Schritt: Gilt für alle Nachfolger $N(j)$ vom Knoten $K$: $D(K) + k_{Kj} < D(j)$, so wird $D(j) = D(K) + k_{Kj}, V(j) = K$ gesetzt und der Knoten $j$ wird mit in die Menge $m$ aufgenommen.

3. Schritt: Der ausgewählte Knoten $K \in M$ wird aus der Menge entfernt.

Die Schritte 1-3 werden so lange wiederholt bis gilt $M = \{ \}$.

Die Vorgehensweise soll im Folgenden anhand eines Beispiels demonstriert werden.

Beispiel: Dijkstra-Algorithmus

FIFO-Algorithmus

Beispiel

Gegeben sei der obige Diagraph. Für diesen soll nach dem Dijkstra-Algorithmus der kürzeste Weg von einem Startknoten zu allen anderen Knoten bestimmt werden.

Begonnen wird mit der Initialisierung:

Als Startknoten wird der Knoten 1 gewählt:

$M = \{1 \}$,

$D(1) = 0$,

$D(i) = \infty$ für die Knoten $i = 2,3,4,5,6$ und

$V(i) = -$ für alle Knoten $i = 1,2,3,4,5,6$.


Das Ganze wird in eine Tabelle eingetragen:

$i$   $1$      $2$      $3$      $4$      $5$      $6$   
$D(i)$           $0$   $\infty$   $\infty$   $\infty$   $\infty$   $\infty$   
$V(i)$           $-$$-$$-$$-$$-$$-$
$M$            $x$     

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 $x$. Dem Startknoten 1 wird $D(1) = 0$ zugeordnet, allen anderen Knoten $D(i) = \infty$. $V(i)$ 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 $K$ ausgewählt, welcher sich in $M$ befindet und den kürzesten Weg $D(i)$ aufweist. In $M$ befindet sich zunächst der Startknoten 1, also $K = 1$. 

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 $D(1) = 0$ zur Pfeilbewertung des Nachfolgerknotens addiert:

$D(1) + k_{12} = 0 + 120 = 120$. 

Das Ergebnis wird mit dem kürzesten Weg des Nachfolgerknotens $D(2) = \infty$ verglichen:

$D(1) + k_{12} < D(2)$

$120 < \infty$.

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

Es gilt also $120 < \infty$ und demnach wird $D(2) = 120$ gesetzt. Der Vorgänger von Knoten $2$ ist demnach Knoten $1$:

$V(2) = 1$.


Knoten 3:

Für den Knoten 3 gilt dieselbe Vorgehensweise:

$D(1) + k_{13} = 0 + 30 = 30 < \infty$

$D(3) = 30$.

$V(3) = 1$.

3. Schritt: 

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

Die neue Tabelle ergibt sich zu:

$i$   $1$      $2$      $3$   $4$$5$$6$
$D(i)$            $0$$120$$30$$\infty$$\infty$$\infty$
$V(i)$            $-$$1$$1$$-$$-$$-$
$M$             $x$$x$   

2. Iteration

1. Schritt: 

Zunächst wird ein Knoten $K$ ausgewählt, welcher sich in $M$ befindet und den kürzesten Weg $D(i)$ aufweist. In $M$ befinden sich die Knoten 1 und 2. Den kürzesten Weg besitzt Knoten 3 mit $D(3) = 30$. 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:

$D(3) + k_{34} < D(4)$

$30 + 100 = 130 < \infty$

$D(4) = 130$.

$V(4) = 3$.

Knoten 5: 

$D(3) + k_{35} < D(5)$

$30 + 45 = 75 < \infty$

$D(5) = 75$.

$V(5) = 3$.

3. Schritt: 

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

$i$   $1$      $2$      $3$      $4$      $5$      $6$   
$D(i)$            $0$$120$$30$$130$$75$$\infty$
$V(i)$            $-$$1$$1$$3$$3$-
$M$             $x$ $x$$x$ 

3. Iteration

1. Schritt: 

Zunächst wird ein Knoten $K$ ausgewählt, welcher sich in $M$ befindet und den kürzesten Weg $D(i)$ aufweist. In $M$ befinden sich die Knoten 2, 4 und 5. Den kürzesten Weg besitzt Knoten 5 mit $D(5) = 75$. 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:

$D(5) + k_{54} < D(4)$

$75 + 35 = 110 < 130$

$D(4) = 110$.

$V(4) = 5$.

Knoten 6: 

$D(5) + k_{56} < D(6)$

$75 + 40 = 115 < \infty$

$D(6) = 115$.

$V(6) = 5$.

3. Schritt: 

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

$i$   $1$      $2$      $3$      $4$      $5$      $6$   
$D(i)$            $0$$120$$30$$110$$75$$115$
$V(i)$            $-$$1$$1$$5$$3$$5$
$M$             $x$ $x$ $x$

4. - 6. Iteration

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

$D(4) + k_{42} > D(2)$: $110 + 80 > 120$. Der Vorgänger bleibt Knoten $1$.

$D(4) + k_{46} > D(6)$: $110 + 40 > 120$. Der Vorgänger bleibt Knoten $5$.

Der Knoten $4$ wird aus $M$ entfernt. 

$i$   $1$      $2$      $3$      $4$      $5$      $6$   
$D(i)$            $0$$120$$30$$110$$75$$115$
$V(i)$            $-$$1$$1$$5$$3$$5$
$M$              $x$   $x$

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

$D(6) + k_{64} > D(4)$: $115 + 35 > 110$. Der Vorgänger bleibt Knoten $5$.

Der Knoten 6 wird aus $M$ entfernt. 

$i$   $1$      $2$      $3$      $4$      $5$      $6$   
$D(i)$            $0$$120$$30$$110$$75$$115$
$V(i)$            $-$$1$$1$$5$$3$$5$
$M$             $x$    

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

$D(2) + k_{23} > D(3)$: $120 + 35 > 30$. Der Vorgänger bleibt Knoten $1$.

Der Knoten 2 wird aus $M$ 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:

$4 - 5 - 3 - 1$

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