Lektion 3.2

Kürzeste Wege mit dem Algorithmus von Dijkstra

30 min Lesezeit

Ein Navigationsgerät sucht nicht den Weg mit den wenigsten Abbiegungen, sondern den mit der kürzesten Fahrzeit. Die Breitensuche aus der letzten Lektion zählt aber nur Kanten und behandelt jede Straße gleich. Sobald die Kanten Gewichte tragen (Länge in Kilometern, Fahrzeit, Kosten), brauchen wir ein Verfahren, das Gewichte aufsummiert.

Der Niederländer Edsger Dijkstra hat 1956 ein Verfahren gefunden, das dieses Problem effizient löst. Seine Grundidee ist einfach: Der Knoten, der von allen noch nicht fertig behandelten Knoten am nächsten am Start liegt, kann sich nicht mehr verbessern, denn jeder andere Weg zu ihm müsste über einen Knoten laufen, der mindestens ebenso weit weg ist. Das Verfahren fixiert also immer den nächsten Knoten, und der Abstand der übrigen wird laufend verbessert. Im Werkzeug Graphalgorithmen kannst du das Verfahren auf eigenen Graphen schrittweise nachvollziehen.

Definition

Gewichteter Graph und kürzester Weg

Ein gewichteter Graph ordnet jeder Kante $e$ ein Gewicht $w(e)$ zu. Das Gewicht eines Weges ist die Summe der Gewichte seiner Kanten. Ein kürzester Weg von $s$ nach $v$ ist ein Weg mit kleinstem Gesamtgewicht, und dieses Gewicht heißt der Abstand $d(s, v)$ .

Der kürzeste Weg nach Gewicht ist nicht immer der mit den wenigsten Kanten: Eine Umleitung über viele kurze Straßen kann schneller sein als eine einzige lange.

d(s,v) = \min \Bigl\{ \sum_{e \in P} w(e) \;:\; P \text{ ist ein Weg von } s \text{ nach } v \Bigr\}

Definition

Algorithmus von Dijkstra

Für jeden Knoten $v$ führst du einen vorläufigen Abstand $\text{dist}(v)$ und kennzeichnest Knoten als fertig oder offen. Am Anfang gilt $\text{dist}(s) = 0$ und für alle anderen Knoten $\infty$ .

1. Wähle unter den offenen Knoten den mit dem kleinsten vorläufigen Abstand, nenne ihn $u$ , und markiere ihn als fertig. Sein Abstand ist jetzt endgültig.
2. Entspanne alle Kanten $(u, v)$ zu offenen Nachbarn: Wenn der Weg über $u$ kürzer ist als der bisher bekannte, setze den Abstand neu.
3. Wiederhole, bis alle Knoten fertig sind (oder der gesuchte Zielknoten fertig ist).

Voraussetzung: Alle Gewichte müssen nichtnegativ sein. Bei negativen Kantengewichten ist der Beweis nicht mehr gültig, und das Verfahren kann falsche Ergebnisse liefern. Mit einer Prioritätswarteschlange (Heap) beträgt die Laufzeit $O((|V| + |E|) \log |V|)$ .

\text{dist}(v) \leftarrow \min\bigl(\text{dist}(v),\ \text{dist}(u) + w(u,v)\bigr)

Beispiel

Dijkstra von $S$ aus

Gegeben sind die Knoten $S, A, B, C, T$ und die ungerichteten Kanten mit Gewichten: $S\!-\!A$ : $4$ , $S\!-\!B$ : $1$ , $B\!-\!A$ : $2$ , $A\!-\!C$ : $1$ , $B\!-\!C$ : $5$ , $C\!-\!T$ : $3$ .

Start: $\text{dist}(S) = 0$ , alle anderen $\infty$ .

Schritt 1: $S$ ist fertig (Abstand $0$ ). Entspannen: $A = 4$ , $B = 1$ .

Schritt 2: Kleinster offener Abstand ist $B = 1$ , also $B$ fertig. Entspannen: $A$ über $B$ kostet $1 + 2 = 3 < 4$ , setze $A = 3$ . $C$ über $B$ kostet $1 + 5 = 6$ , setze $C = 6$ .

Schritt 3: Kleinster offener Abstand ist $A = 3$ , also $A$ fertig. Entspannen: $C$ über $A$ kostet $3 + 1 = 4 < 6$ , setze $C = 4$ .

Schritt 4: $C = 4$ fertig. Entspannen: $T = 4 + 3 = 7$ . Schritt 5: $T = 7$ fertig.

d(S,B) = 1,\quad d(S,A) = 3,\quad d(S,C) = 4,\quad d(S,T) = 7

Der kürzeste Weg nach $T$ ist $S, B, A, C, T$ mit Gesamtgewicht $1 + 2 + 1 + 3 = 7$ . Er hat vier Kanten; der Weg $S, A, C, T$ hätte nur drei Kanten, aber das Gewicht $4 + 1 + 3 = 8$ . Gerade solche Fälle löst die Breitensuche falsch.

Zusammenfassung

In einem gewichteten Graphen ist der kürzeste Weg der mit dem kleinsten Gesamtgewicht, nicht der mit den wenigsten Kanten.
Dijkstra fixiert immer den offenen Knoten mit dem kleinsten vorläufigen Abstand und entspannt dessen ausgehende Kanten.
Voraussetzung: alle Kantengewichte sind nichtnegativ.
Mit einer Prioritätswarteschlange ist die Laufzeit $O((|V|+|E|)\log|V|)$ .
Mit gespeicherten Vorgängern lässt sich der Weg selbst rekonstruieren.

Übungen

Aufgabe 1Numerisch

Wie groß ist im Beispielgraphen der kürzeste Abstand von $S$ nach $C$ ?

Aufgabe 2Multiple Choice

Warum darf der Algorithmus von Dijkstra keine negativen Kantengewichte enthalten?

Aufgabe 3Numerisch

Ein ungerichteter Graph hat die Kanten $X\!-\!Y$ : $2$ , $X\!-\!Z$ : $7$ , $Y\!-\!Z$ : $3$ , $Y\!-\!W$ : $8$ , $Z\!-\!W$ : $1$ . Bestimme den kürzesten Abstand von $X$ nach $W$ .

Aufgabe 4Freitext

Erkläre, warum die Breitensuche für gewichtete Graphen nicht den kürzesten Weg nach Gewicht liefert, und gib ein Beispiel an.

Dijkstra von SSS aus

Zusammenfassung

Übungen

Dijkstra von $S$ aus