Algorithmus von Dinic

ein Algorithmus zur Bestimmung des maximalen Fluss in einem Netzwerk

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

Bearbeiten

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

Der Algorithmus arbeitet wie folgt:

  1. Setze   für jede Kante  .
  2. Bestimme den Schichtgraphen  .
  3. Bestimme einen Sperrfluss   in  .
  4. Falls   der Nullfluss ist, sind wir fertig, ansonsten augmentiere   entlang   (d. h. für jede Kante   setze:   (mit  , falls  )) und springe zu 2.

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

Sperrfluss finden

Bearbeiten

Für Schritt 3 des Algorithmus kann ein Sperrfluss   in   beispielsweise wie folgt berechnet werden:

  1. Setze   für jede Kante  .
  2. Setze  .
  3. START
    •   (Weg aus nur einem Knoten ohne Kanten)
    •  
    • springe zu VOR.
  4. VOR
    • Falls in   keine Kante den Knoten   verlässt, springe zu ZURÜCK.
    • Anderenfalls
      • Wähle eine Kante   aus  .
      • Verlängere   um  .
      •  
      • Falls  , springe zu VOR.
      • Falls  , springe zu AUGMENTIEREN.
  5. AUGMENTIEREN
    • Augmentiere   längs   um so viel wie möglich (d. h. für   setze   für jedes  ).
    • Entferne die Kanten aus  , die dadurch ausgelastet werden.
    • Springe zu START.
  6. ZURÜCK
    • Falls  , ist   Sperrfluss, also STOP.
    • Anderenfalls
      • Sei   letzte Kante auf  .
      • Verkürze   um  .
      • Entferne   und alle mit ihm inzidenten Kanten aus  .
      •  
      • Springe zu VOR.

Am Ende dieses Verfahrens ist   Sperrfluss in  . Sei   und  . Dieses Verfahren benötigt für die Berechnung eines Sperrflusses eine Laufzeit von  . Denn jeder Aufruf von AUGMENTIEREN benötigt Laufzeit   und jeder dieser Aufrufe nimmt eine Kante aus dem Graphen, also gibt es höchstens   dieser Aufrufe (denn der Schichtgraph   hat höchstens   Kanten). Weil der Schichtgraph   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   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  -mal durchgeführt, alle ZURÜCK-Operationen zusammen haben eine Laufzeit von  .

Anmerkung

Bearbeiten

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

Bearbeiten

Sei   und  . Der Algorithmus von Dinic benötigt höchstens   Durchläufe. Der Schichtgraph   kann mit Breitensuche in Laufzeit   berechnet werden. Ein Sperrfluss in   kann mit der oben angegebenen Methode in Laufzeit   berechnet werden. Damit ergibt sich eine Gesamtlaufzeit von  . 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   erreichen.

Bearbeiten