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: 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