Algorithmus von Dinic – Wikipedia

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 | Quelltext 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 | Quelltext 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 .

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