Algorithmus von Dinic

Der Algorithmus von Dinic ist ein Algorithmus aus der Graphentheorie zur Bestimmung eines maximalen s-t-Flusses in einem Netzwerk. Er wurde von E. A. Dinic (Jefim (Chaim) Dinic) entwickelt und 1970 publiziert. Er ist eine Weiterentwicklung des Edmonds-Karp-Algorithmus, den Dinic unabhängig von Jack Edmonds und Richard M. Karp entwickelte. Der Algorithmus von Dinic unterscheidet sich vom Edmonds-Karp-Algorithmus, indem in jedem Durchgang nicht nur an einem einzelnen kürzesten s-t-Weg augmentiert wird, sondern mitunter an größeren s-t-Flüssen, die sich aus mehreren kürzesten s-t-Wegen zusammensetzen.

Der Algorithmus

Im Folgenden bezeichnet im Netzwerk $(G, u, s, t)$ $G$ den gerichteten Graphen, $u\colon E(G) \rightarrow \mathbb{R}_+$ die Kapazitätsfunktion (wobei $u(e)$ die Kapazität einer Kante $e$ angibt), $s$ den Knoten, von dem der Fluss startet, und $t$ den Zielknoten des Flusses. $V(G)$ bezeichnet die Knotenmenge des Graphen $G$ und $E(G)$ die Kantenmenge. Zu einem Fluss $f$ bezeichnet $G_f$ den Residualgraphen und $G_f^L$ den Schichtgraphen, also den Graphen, der sich mit $G$ die Knotenmenge teilt und aus genau den Kanten $(u,v)\in E(G_f)$ besteht, die für beliebige Knoten $u$ und $v$ zu einem kürzesten s-v-Weg von $G_f$ gehören. Insbesondere enthält $G_f^L$ auch alle Kanten, die zu einem kürzesten s-t-Weg in $G_f$ gehören. $u_f$ bezeichnet die zum Residualgraph gehörige Residualkapazität. Ein Sperrfluss (auch blockierender Fluss genannt) in $G_f^L$ ist ein s-t-Fluss, der in jedem s-t-Weg in $G_f^L$ mindestens eine Kante auslastet. Zu einer Kante $e\in E(G)$ bezeichnet $\overleftarrow{e}$ die zugehörige Rückkante des Residualgraphen.

Der Algorithmus arbeitet wie folgt:

1. Setze $f(e):=0$ für jede Kante $e\in E(G)$.
2. Bestimme den Schichtgraphen $G_f^L$.
3. Bestimme einen Sperrfluss $g$ in $G_f^L$.
4. Falls $g$ der Nullfluss ist, sind wir fertig, ansonsten augmentiere $f$ entlang $g$ (d.h. für jede Kante $e\in E(G)$ setze: $f(e):=f(e)+g(e)-g(\overleftarrow{e})$ (mit $g(e):=0$, falls $e\notin E(G_f^L)$)) und springe zu 2.

Am Ende ist $f$ ein maximaler s-t-Fluss, da es im Residualgraphen $G_f$ keinen s-t-Weg mehr gibt.

Sperrfluss finden

Für Schritt 3 des Algorithmus kann ein Sperrfluss $g$ in $G_f^L$ beispielsweise wie folgt berechnet werden:

1. Setze $g(e):=0$ für jede Kante $e\in G_f^L$.
2. Setze $H:=G_f^L$.
3. START
   • $P:=[s]$ (Weg aus nur einem Knoten ohne Kanten)
   • $v:=s$
   • springe zu VOR.
4. VOR
   • Falls in $H$ keine Kante den Knoten $v$ verlässt, springe zu ZURÜCK.
   • Anderenfalls
     • Wähle eine Kante $(v,w)$ aus $H$.
     • Verlängere $P$ um $(v,w)$.
     • $v:=w$
     • Falls $v\neq t$, springe zu VOR.
     • Falls $v=t$, springe zu AUGMENTIEREN.
5. AUGMENTIEREN
   • Augmentiere $g$ längs $P$ um so viel wie möglich (d.h. für $\gamma := \min_{e\in E(P)}u_f(e)$ setze $g(e):=g(e)+\gamma\!\,$ für jedes $e\in E(P)$).
   • Entferne die Kanten aus $H$, die dadurch ausgelastet werden.
   • Springe zu START.
6. ZURÜCK
   • Falls $v=s$, ist $g$ Sperrfluss, also STOP.
   • Anderenfalls
     • Sei $(u,v)$ letzte Kante auf $P$.
     • Verkürze $P$ um $(u,v)$.
     • Entferne $v$ und alle mit ihm inzidenten Kanten aus $H$.
     • $v:=u$
     • Springe zu VOR.

Am Ende dieses Verfahrens ist $g$ Sperrfluss in $G_f^L$. Sei $m=|E(G)|$ und $n=|V(G)|$. Dieses Verfahren benötigt für die Berechnung eines Sperrflusses eine Laufzeit von $\mathcal{O}(n m)$. Denn jeder Aufruf von AUGMENTIEREN benötigt Laufzeit $\mathcal{O}(n)$ und jeder dieser Aufrufe nimmt eine Kante aus dem Graphen, also gibt es höchstens $m$ dieser Aufrufe (denn der Schichtgraph $G_f^L$ hat höchstens $m$ Kanten). Weil der Schichtgraph $G_f^L$ keine gerichteten Kreise enthält, kann zwischen zwei AUGMENTIEREN-Aufrufen jeder Knoten höchstens einmal durch eine VOR-Operation erreicht werden, also werden insgesamt höchstens $\mathcal{O}(n m)$ solche durchgeführt; eine VOR-Operation kann in konstanter Laufzeit ausgeführt werden. In den ZURÜCK-Operationen wird jedes mal ein Knoten entfernt, also werden sie höchstens $n$-mal durchgeführt, alle ZURÜCK-Operationen zusammen haben eine Laufzeit von $\mathcal{O}(n+m)$.

Anmerkung

E. A. Dinic arbeitete statt mit dem Schichtgraphen mit einem Teilgraphen, der genau aus den Knoten und Kanten besteht, die auf kürzesten s-t-Wegen liegen. Die Verwendung des Schichtgraphen funktioniert analog, vereinfacht aber die Beschreibung des Algorithmus.

Laufzeit

Sei $m=|E(G)|$ und $n=|V(G)|$. Der Algorithmus von Dinic benötigt höchstens $n-1$ Durchläufe. Der Schichtgraph $G_f^L$ kann mit Breitensuche in Laufzeit $\mathcal{O}(m)$ berechnet werden. Ein Sperrfluss in $G_f^L$ kann mit der oben angegebenen Methode in Laufzeit $\mathcal{O}(n m)$ berechnet werden. Damit ergibt sich eine Gesamtlaufzeit von $\mathcal{O}(n^2 m)$. Dies ist auch die Laufzeit, die von Dinic 1970 bewiesen wurde. Allerdings arbeitet der Goldberg-Tarjan-Algorithmus schneller.

Mit einer Verbesserung von Alexander Karzanov von 1974 lässt sich für den Algorithmus von Dinic auch eine Laufzeit von $\mathcal{O}(n^3 + nm)$ erreichen.

Quellen

• Bernhard Korte, Jens Vygen: Kombinatorische Optimierung: Theorie und Algorithmen. Aus dem Englischen von Rabe von Randow. Springer-Verlag, Berlin Heidelberg 2008, ISBN 978-3-540-76918-7
• Helmut Alt: Vorlesungsskript Höhere Algorithmik, Wintersemester 2006/2007, Freie Universität Berlin.

Weblinks

• E. A. Dinic: Algorithm for solution of a problem of maximum flow in a network with power estimaton, 1970 – E. A. Dinics Veröffentlichung des Algorithmus