Algorithmus von Dinic

Der Algorithmus v​on Dinic i​st ein Algorithmus a​us der Graphentheorie z​ur Bestimmung e​ines maximalen Flusses i​n einem Netzwerk. Er w​urde von E. A. Dinic (Jefim (Chaim) Dinic) entwickelt u​nd 1970 publiziert. Er i​st eine Weiterentwicklung d​es Edmonds-Karp-Algorithmus, d​en Dinic unabhängig v​on Jack Edmonds u​nd Richard M. Karp entwickelte. Der Algorithmus v​on Dinic unterscheidet s​ich vom Edmonds-Karp-Algorithmus, i​ndem in j​edem Durchgang n​icht nur a​n einem einzelnen kürzesten s-t-Weg augmentiert wird, sondern mitunter a​n größeren s-t-Flüssen, d​ie sich a​us mehreren kürzesten s-t-Wegen zusammensetzen.

Der Algorithmus

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

Der Algorithmus arbeitet w​ie folgt:

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

Am Ende ist ${\displaystyle f}$ ein maximaler s-t-Fluss, da es im Residualgraphen ${\displaystyle G_{f}}$ keinen s-t-Weg mehr gibt.

Sperrfluss finden

Für Schritt 3 des Algorithmus kann ein Sperrfluss ${\displaystyle g}$ in ${\displaystyle G_{f}^{L}}$ beispielsweise wie folgt berechnet werden:

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

Am Ende dieses Verfahrens ist ${\displaystyle g}$ Sperrfluss in ${\displaystyle G_{f}^{L}}$. Sei ${\displaystyle m=|E(G)|}$ und ${\displaystyle n=|V(G)|}$. Dieses Verfahren benötigt für die Berechnung eines Sperrflusses eine Laufzeit von ${\displaystyle {\mathcal {O}}(nm)}$. Denn jeder Aufruf von AUGMENTIEREN benötigt Laufzeit ${\displaystyle {\mathcal {O}}(n)}$ und jeder dieser Aufrufe nimmt eine Kante aus dem Graphen, also gibt es höchstens ${\displaystyle m}$ dieser Aufrufe (denn der Schichtgraph ${\displaystyle G_{f}^{L}}$ hat höchstens ${\displaystyle m}$ Kanten). Weil der Schichtgraph ${\displaystyle 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 ${\displaystyle {\mathcal {O}}(nm)}$ 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 ${\displaystyle n}$-mal durchgeführt, alle ZURÜCK-Operationen zusammen haben eine Laufzeit von ${\displaystyle {\mathcal {O}}(n+m)}$.

Anmerkung

E. A. Dinic arbeitete s​tatt mit d​em Schichtgraphen m​it einem Teilgraphen, d​er genau a​us den Knoten u​nd Kanten besteht, d​ie auf kürzesten s-t-Wegen liegen. Die Verwendung d​es Schichtgraphen funktioniert analog, vereinfacht a​ber die Beschreibung d​es Algorithmus.

Laufzeit

Sei ${\displaystyle m=|E(G)|}$ und ${\displaystyle n=|V(G)|}$. Der Algorithmus von Dinic benötigt höchstens ${\displaystyle n-1}$ Durchläufe. Der Schichtgraph ${\displaystyle G_{f}^{L}}$ kann mit Breitensuche in Laufzeit ${\displaystyle {\mathcal {O}}(m)}$ berechnet werden. Ein Sperrfluss in ${\displaystyle G_{f}^{L}}$ kann mit der oben angegebenen Methode in Laufzeit ${\displaystyle {\mathcal {O}}(nm)}$ berechnet werden. Damit ergibt sich eine Gesamtlaufzeit von ${\displaystyle {\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 ${\displaystyle {\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. (PDF; 2,5 MB)

Weblinks

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