IMG_1224.jpeg

## Algorithmus von Dijkstra ### Problemstellung Gegeben sei ein Graph $G = (V, E)$ mit Kantengewichten $w: E \rightarrow \mathbb{R}_{\geq 0}$ und ein Startknoten $s \in V$. Finde die kürzesten Wege von $s$ zu allen anderen Knoten $v \in V$. ### Idee Der Algorithmus von Dijkstra ist ein Greedy-Algo...

## Algorithmus von Dijkstra ### Problemstellung Gegeben sei ein Graph $G = (V, E)$ mit Kantengewichten $w: E \rightarrow \mathbb{R}_{\geq 0}$ und ein Startknoten $s \in V$. Finde die kürzesten Wege von $s$ zu allen anderen Knoten $v \in V$. ### Idee Der Algorithmus von Dijkstra ist ein Greedy-Algorithmus, der die Knoten in der Reihenfolge ihrer Entfernung vom Startknoten $s$ besucht. Dabei wird für jeden besuchten Knoten $v$ dieDistanz $d[v]$ von $s$ zu $v$ gespeichert. ### Algorithmus 1. **Initialisierung:** * Setze $d[s] = 0$ und $d[v] = \infty$ für alle $v \in V \setminus \{s\}$. * Setze $Q = V$ (alle Knoten sind unbesucht). 2. **Iteration:** * Solange $Q \neq \emptyset$: * Finde $u \in Q$ mit minimalem $d[u]$. * Entferne $u$ aus $Q$. * Für alle Nachbarn $v$ von $u$: * Wenn $d[v] > d[u] + w(u, v)$: * Setze $d[v] = d[u] + w(u, v)$. * Setze $\pi[v] = u$ (Vorgänger von $v$ auf dem kürzesten Weg von $s$ zu $v$). ### Beispiel #### Graph Der Graph besteht aus 5 Knoten (A, B, C, D, E) und den folgenden Kanten mit Gewichten: | Knoten | Knoten | Gewicht | | :----: | :----: | :-----: | | A | B | 10 | | A | C | 3 | | B | C | 1 | | B | D | 2 | | C | B | 4 | | C | D | 8 | | C | E | 2 | | D | E | 7 | | E | D | 9 | #### Ablauf Starte mit Knoten A. * Initialisierung: * $d[A] = 0, d[B] = \infty, d[C] = \infty, d[D] = \infty, d[E] = \infty$ * $Q = \{A, B, C, D, E\}$ * Iteration 1: * $u = A$ (da $d[A] = 0$ minimal ist) * $Q = \{B, C, D, E\}$ * Nachbarn von A: $B, C$ * $d[B] = \min\{\infty, 0 + 10\} = 10, \pi[B] = A$ * $d[C] = \min\{\infty, 0 + 3\} = 3, \pi[C] = A$ * Iteration 2: * $u = C$ (da $d[C] = 3$ minimal ist) * $Q = \{B, D, E\}$ * Nachbarn von C: $B, D, E$ * $d[B] = \min\{10, 3 + 4\} = 7, \pi[B] = C$ * $d[D] = \min\{\infty, 3 + 8\} = 11, \pi[D] = C$ * $d[E] = \min\{\infty, 3 + 2\} = 5, \pi[E] = C$ * Iteration 3: * $u = E$ (da $d[E] = 5$ minimal ist) * $Q = \{B, D\}$ * Nachbarn von E: $D$ * $d[D] = \min\{11, 5 + 9\} = 11, \pi[D] = C$ (keine Änderung) * Iteration 4: * $u = B$ (da $d[B] = 7$ minimal ist) * $Q = \{D\}$ * Nachbarn von B: $D$ * $d[D] = \min\{11, 7 + 2\} = 9, \pi[D] = B$ * Iteration 5: * $u = D$ (da $d[D] = 9$ minimal ist) * $Q = \{\}$ * Nachbarn von D: $E$ * $d[E] = \min\{5, 9 + 7\} = 5, \pi[E] = C$ (keine Änderung) #### Ergebnis Kürzeste Wege von A zu allen anderen Knoten: * $d[A] = 0$ * $d[B] = 7, \text{Weg: } A \rightarrow C \rightarrow B$ * $d[C] = 3, \text{Weg: } A \rightarrow C$ * $d[D] = 9, \text{Weg: } A \rightarrow C \rightarrow B \rightarrow D$ * $d[E] = 5, \text{Weg: } A \rightarrow C \rightarrow E$ ### Eigenschaften #### Laufzeit Die Laufzeit des Algorithmus von Dijkstra hängt von der Implementierung der Priority Queue $Q$ ab. * Mit einem Array: $O(|V|^2 + |E|) = O(|V|^2)$ * Mit einer Binary Heap: $O((|V| + |E|) \log |V|) = O(|E| \log |V|)$ (für zusammenhängende Graphen) * Mit einer Fibonacci Heap: $O(|E| + |V| \log |V|)$ #### Korrektheit Der Algorithmus von Dijkstra findet immer die kürzesten Wege, wenn alle Kantengewichte nicht-negativ sind. #### Bemerkungen * Der Algorithmus funktioniert nicht mit negativen Kantengewichten. In diesem Fall muss der Algorithmus von Bellman-Ford verwendet werden. * Der Algorithmus kann auch verwendet werden, um den kürzesten Weg zwischen zwei bestimmten Knoten zu finden. In diesem Fall kann der Algorithmus abgebrochen werden, sobald der Zielknoten besucht wurde.