Algorithmus von Dinic

Der Algorithmus von Dinic ist ein Algorithmus aus der Graphentheorie zur Bestimmung eines maximalen 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 ${\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 wie 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 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 ${\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