7. Graphen mit Kantenkosten

7.1 Kürzeste Wege: Dijkstras Algorithmus

Hier sehen Sie einen Graphen mit Kantengewichten:

Was ist der kürzeste Pfad von \(s\) nach \(t\) in diesem Graphen? Wenn es Ihnen nur um die Zahl der Kanten geht, dann gibt es einen Pfad der Länge 3. Dieser hat aber Gesamtkosten von 12. In der Tat gibt es einen billigeren.

An dieser Stelle benötigen wir ein paar formale Definition. Wir haben einen gerichteten Graphen \(G = (V,E)\) und eine Kantenkostenfunktion \(c : V \rightarrow \R^+_0\). Die Kosten eines Pfades \(p = u_0, u_1, \dots, u_k\) sind

\begin{align*} c (p) := c(u_0, u_1) + c(u_1, u_2) + \dots + c(u_{k-1}, u_k) \ . \end{align*}

Für Knoten \(u, v \in V\) definieren wir

\begin{align*} \dist(u,v) := \min \{ c(p) \ | \ \textnormal{$p$ ist ein Pfad von $s$ nach $t$}\} \ . \end{align*}

Insbesondere gilt \(\dist(u,u) = 0\), da \(u\) selsbt als Pfad der Länge 0 gilt, von \(u\) nach \(u\) führt und darüberhinaus Gesamtkosten \(0\) hat. Um nun in einem Graphen mit Kantenkosten den billigsten Pfad von \(s\) nach \(t\) zu finden, reicht Tiefensuche nicht mehr aus. Allerdings können wir uns von der Idee der Tiefensuche inspirieren lassen. Stellen wir uns vor, wir schicken von \(s\) aus eine Armee von Ameisen los, die mit konstanter Geschwindigkeit den Graphen erkunden und für eine Kante von Kosten \(c\) genau \(c\) Sekunden benötigen. Das Ergebnis ist als Dijkstras Algorithmus bekannt. Hier eine Animation.

Wir sehen: der Zeitpunkt \(k\) zu welchem die Ameisen einen Knoten \(v\) erreichen, ist gleich dem Abstand \(\dist(s,v)\).

Dijkstras Algorithmus

Die Frage ist nun, wie wir diese Ameisenerkundung im Rechner simulieren. Hierfür merken wir uns für jeden Knoten eine estimated time of arrival, die erwartete Ankunftszeit der Ameisen, und kürzen diese mit $\ETA(u)$ ab. Diese repräsentiert im Prinzip den besten Schätzwert, den wir aufgrund des bisher erkundeten Teil des Graphen berechnet haben. Darüberhinaus merken wir uns die Menge $\Reached$ der Knoten, die bereits von den Ameisen erreicht worden ist. Wir initialisieren $\ETA(s) = 0$ und $\ETA(u) = \infty$ für jeden anderen Knoten; wir initialisieren $\Reached = \emptyset$.

Die folgende Animation ist fast die gleiche wie oben, nur dass wir nun $\Reached$ rot markieren und Knoten außerhalb von $\Reached$, die bereits einen endlichen $\ETA$-Wert haben (also im Prinzip die Nachbarn von $\Reached$), blau markieren. Die Werte $\ETA(u)$ stehen als rote oder blaue Zahlen neben den Knoten - außer wenn $\ETA(u) = \infty$ ist; dann lassen wir sie aus Gründen der Übersichtlichkeit einfach weg:

Die $\ETA$-Werte ändern sich also, weil wir im Verlauf des Prozesses bessere Pfade entdecken. Um diesen Ameisenprozess nun auf einem Rechner simulieren zu können (sprich: um einen Algorithmus implementieren zu können), machen wir folgende Beobachtung: der Knoten $u \in V \setminus \Reached$ mit dem kleinsten $\ETA$-Wert ist der nächste, der von den Ameisen erreicht wird und somit der Menge $\Reached$ hinzugefügt wird. In einer Implementierung müssen wir uns natürlich noch für jeden Knoten $v$ den Vorgängerknoten merken, über den die Ameisen ihn erreicht haben: $\pred[v]$.

1. def Dijkstra ($G = (V,E)$, $c : V \rightarrow \R^+$, $s \in V$)
   1. $\ETA(u) := \infty$ für alle $u \in V$
   2. $\ETA(s) := 0$
   3. $\Reached = \emptyset$
   4. $\pred(u) := \texttt{null}$ für alle $u \in V$
   5. while $\Reached \ne V$:
      1. $v := \textnormal{argmin} \{\ETA(v) \ | \ v \in V \setminus \Reached \}$
      2. for $(v,w) \in E$:
         1. if $\ETA(v) + c(v,w) \lt \ETA(w)$:
            1. $\ETA(w) := \ETA(v) + c(v,w)$
            2. $\pred(w) := \pred(v)$
      3. füge $v$ der Menge $\Reached$ hinzu
   6. return $(\ETA,\pred)$

Eine Kuriosität dieser Implementierung ist, dass schlussendlich jeder Knoten erreicht wird; selbst wenn es von $s$ zu ihm gar keinen Pfad gibt. Wenn nämlich alle von $s$ aus erreichbaren Knoten in $\Reached$ gelandet sind, wird in Zeile 7 einfach in $v$ mit $\ETA(v) = \infty$ genommen. Alternativ können wir uns vorstellen, dass wir für jedes Paar $(v,w) \in V \times V \setminus E$ eine Kante einfügen und $c(v,w) = \infty$ setzen. Dies sind aber nur kosmetische Änderungen.

Korrektheit

Wenn Sie zufrieden damit sind, wie wir den Ameisenprozess im Rechner simulieren, dann können Sie diesen Abschnitt überspringen. Wenn Ihnen mathematische Korrektheitsbeweise gefallen, dann lesen Sie ihn. Es illustriert sehr schön die Methode der Schleifeninvariante. Auch werden wir im nächsten Teilkapitel - wo wir negative Kantenkosten zulassen - untersuchen, warum Dijkstra das nicht kann und woran der folgende Korrektheitsbeweis scheitert.

Wir können also den günstigsten Pfad von $s$ nach $t$ finden, indem wir $v := t$ initialisieren und dann iterativ $v := \pred(v)$ setzen, bis $v = s$ gilt.

Um Theorem 7.1 zu beweisen, müssen wir, wie so oft, eine stärkere Behauptung formulieren; nämlich eine Schleifenvariante finden, die zu jedem Zeiptunkt gilt und aus der dann die Behauptung des Theorems folgt. Zuerst führen wir etwas Terminologie ein: sei $p$ ein Pfad von $s$ zu einem Knoten $w$ und $V(p)$ die Menge der Knoten drauf. Wir nennen den Pfad $p$ einen $\Reached$-Pfad, wenn $V(p) \setminus \{w\} \subseteq \Reached$ gilt; wenn also bis auf möglicherweise den Endpunkt alle Knoten von $p$ in $\Reached$ liegen.

Aus dem Lemma folgt nun, dass in Zeile 13, wenn $\Reached = V$ geworden ist, nun also $\ETA(u) = \dist(s,u)$ für alle Knoten gilt. Für den zweiten Teil des Theorems betrachten wir ein $w$. Wenn $\ETA(w) = \infty$ ist, dann wurden Zeilen 10, 11 nie mit diesem $w$ ausgeführt und $\pred(w) = \texttt{null}$, nach wie vor. Wenn jedoch $\ETA(w) \lt \infty$ ist, dann betrachten wir das letzte Mal, dass Zeilen 10, 11 mit diesem $w$ ausgeführt worden sind (der Wert von $\ETA(w)$ also zum letzten Mal nach unten korrigiert worden ist). Nach Ausführen dieser Zeilen gilt $\ETA(w) = \ETA(v) + c(v,w)$; die Werte $\ETA(v), \ETA(w)$ ändern sich danach nicht mehr ($\ETA(w)$ ändert sich nicht mehr, weil wir ja gerade das letzte Mal betrachten; $\ETA(v)$ ändert sich nicht mehr, weil wir $v$ in $\Reached$ aufnehmen und nach dem Lemma fortan $\ETA(v) = \dist(s,v)$ gilt und $\ETA(v)$ nicht noch kleiner werden kann). Es gilt daher, nachdem Zeilen 10 und 11 zum letzten Mal für dieses $w$ ausgeführt worden sind: $\ETA(w) = \dist(s,w)$ und $\ETA(v) = \dist(s,v)$ und somit gilt auch die zweite Behauptung des Theorems.

Implementierung

Die zentrale Frage ist, wie wir unseren "Kostenvoranschlag" $\ETA$ implementieren.

Variante 1: $\ETA$ als Array. Die Schleife while $\Reached \ne V$ wird genau $n$ mal durchlaufen, da wir in jedem Schritt einen Knoten hinzufügen. Zeilen 10-11 durchlaufen wir für jede Kante $(v,w)$, also insgesamt $m$ mal. Hinzukommen noch die Kosten von Zeile 7. Hier berechnen wir ein argmin, müssen also alle Knoten $v \in V \setminus \Reached$ durchgehen und das mit dem kleinste $\ETA(v)$ finden. Dies benötigt noch einmal $O(n)$ Schritte. Insgesamt erhalten wir eine Laufzeit von \begin{align*} O(n^2 + m) \ . \end{align*}

Variante 2: $\ETA$ als Suchbaum. Wir speichern $\ETA$ in einer Datenstruktur, die uns schnellen Zugriff auf das kleinste Element ermöglicht. Beispielsweise könnten wir irgendeinen balancierten Baum (Rot-Schwarz-Baum, B-Baum, Treap) verwenden mit $\ETA(v)$ als Schlüssel und $v$ als Wert; wir müssten allerdings sicherstellen, dass die Schlüssel alle verschieden sind, also beispielsweise das Paar $(\ETA(v), v)$ selbst als Schlüssel verwenden. Um in Zeile 7 das Argmin zu bestimmen, müssen wir nun einfach den linkesten Knoten im Baum finden. Um in Zeile 10 den Wert von $\ETA(w)$ zu reduzieren, können wir einfach den Knoten löschen und wieder einfügen. Alle diese Operationen brauchen $O(\log n)$ Schritte im Worst-Case. Es ergibt sich eine Laufzeit von \begin{align*} O(m \log n) \end{align*}

Variante 3: $\ETA$ als Heap. In der Tat braucht man hierfür gar keinen Baum. Wir können die Heap-Datenstruktur (ein einfaches Array), die wir von Heapsort in Kapitel 2.4 kennen, nehmen. Da steht das kleinste Schlüssel immer auf Position 0. Entfernen und Hinzufügen braucht $O(\log n)$. Es ergibt sich wieder eine Laufzeit von $O(m \log n)$, allerdings mit einer einfacheren Implementierung und weniger Overhead als wenn wir einen richtigen Suchbaum verwenden.

Varianten 4...: $\ETA$ als Fibonacci-Heap. Eine ausgefeilte Datenstruktur, die auf der Idee des Heaps aufbaut, ist der Fibonacci-Heap (Wikipedia). Dieser weist eine sehr gute amortisierte Laufzeit auf, d.h., manche Operationen können teuer sein, wenn man sie aber über die gesamte "Lebenszeit" der Datenstruktur mittelt, sind sie im Schnitt sehr billig. Insbesondere kann man das kleinste Element in $O(\log n)$ amortisierter Zeit entfernen (wie bei einem normalen Heap); die Kosten eines gegebenen Elementes zu reduzieren - was wir ja in Zeile 7 bis zu $m$ mal tun, und was bei einem Heap $O(\log n)$ kostet - braucht bei Fibonacci-Heaps amortisiert nur $O(1)$ Schritte.