|
Lexikon auf Ihrer Homepage |
|
Lexikon als Lesezeichen hinzufügen |
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.
Inhaltsverzeichnis |
Im Folgenden bezeichnet im Netzwerk <math>(G, u, s, t)</math> <math>G</math> den gerichteten Graphen, <math>u: E(G) \rightarrow \mathbb{R}_+</math> die Kapazitätsfunktion (wobei <math>u(e)</math> die Kapazität einer Kante <math>e</math> angibt), <math>s</math> den Knoten, von dem der Fluss startet, und <math>t</math> den Zielknoten des Flusses. <math>V(G)</math> bezeichnet die Knotenmenge des Graphen <math>G</math> und <math>E(G)</math> die Kantenmenge. Zu einem Fluss <math>f</math> bezeichnet <math>G_f</math> den Residualgraphen und <math>G_f^L</math> den Schichtgraphen, also den Graphen, der sich mit <math>G</math> die Knotenmenge teilt und aus genau den Kanten <math>(u,v)\in E(G_f)</math> besteht, die für beliebige Knoten <math>u</math> und <math>v</math> zu einem kürzesten s-v-Weg von <math>G_f</math> gehören. Insbesondere enthält <math>G_f^L</math> auch alle Kanten, die zu einem kürzesten s-t-Weg in <math>G_f</math> gehören. <math>u_f</math> bezeichnet die zum Residualgraph gehörige Residualkapazität. Ein Sperrfluss (auch blockierender Fluss genannt) in <math>G_f^L</math> ist ein s-t-Fluss, der in jedem s-t-Weg in <math>G_f^L</math> mindestens eine Kante auslastet. Zu einer Kante <math>e\in E(G)</math> bezeichnet <math>\overleftarrow{e}</math> die zugehörige Rückkante des Residualgraphen.
Der Algorithmus arbeitet wie folgt:
Am Ende ist <math>f</math> ein maximaler s-t-Fluss, da es im Residualgraphen <math>G_f</math> keinen s-t-Weg mehr gibt.
Für Schritt 3 des Algorithmus kann ein Sperrfluss <math>g</math> in <math>G_f^L</math> beispielsweise wie folgt berechnet werden:
Am Ende dieses Verfahrens ist <math>g</math> Sperrfluss in <math>G_f^L</math>. Sei <math>m=|E(G)|</math> und <math>n=|V(G)|</math>. Dieses Verfahren benötigt für die Berechnung eines Sperrflusses eine Laufzeit von <math>\mathcal{O}(n m)</math>. Denn jeder Aufruf von AUGMENTIEREN benötigt Laufzeit <math>\mathcal{O}(n)</math> und jeder dieser Aufrufe nimmt eine Kante aus dem Graphen, also gibt es höchstens <math>m</math> dieser Aufrufe (denn der Schichtgraph <math>G_f^L</math> hat höchstens <math>m</math> Kanten). Weil der Schichtgraph <math>G_f^L</math> 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 <math>\mathcal{O}(n m)</math> 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 <math>n</math>-mal durchgeführt, alle ZURÜCK-Operationen zusammen haben eine Laufzeit von <math>\mathcal{O}(n+m)</math>.
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.
Sei <math>m=|E(G)|</math> und <math>n=|V(G)|</math>. Der Algorithmus von Dinic benötigt höchstens <math>n-1</math> Durchläufe. Der Schichtgraph <math>G_f^L</math> kann mit Breitensuche in Laufzeit <math>\mathcal{O}(m)</math> berechnet werden. Ein Sperrfluss in <math>G_f^L</math> kann mit der oben angegebenen Methode in Laufzeit <math>\mathcal{O}(n m)</math> berechnet werden. Damit ergibt sich eine Gesamtlaufzeit von <math>\mathcal{O}(n^2 m)</math>. 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 <math>\mathcal{O}(n^3 + nm)</math> erreichen.
