ZU DEN KURSEN!

Operations Research - Dijkstra-Algorithmus

Kursangebot | Operations Research | Dijkstra-Algorithmus

Operations Research

Dijkstra-Algorithmus

In diesem Abschnitt wird der Dijkstra-Algorithmus zur Bestimmung von kürzesten Wegen in Graphen ausführlich behandelt.

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(i)$ 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.

Anwendungsbeispiel: Dijkstra-Algorithmus

Beispiel Dijkstra-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.