Algorithmus von Dinic

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

Der Algorithmus

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

Der Algorithmus arbeitet wie folgt:

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

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

Sperrfluss finden

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

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

Am Ende dieses Verfahrens ist g Sperrfluss in G_f^L. Sei m = | E(G) | und n = | V(G) | . Dieses Verfahren benötigt für die Berechnung eines Sperrflusses eine Laufzeit von \mathcal{O}(n m). Denn jeder Aufruf von AUGMENTIEREN benötigt Laufzeit \mathcal{O}(n) und jeder dieser Aufrufe nimmt eine Kante aus dem Graphen, also gibt es höchstens m dieser Aufrufe (denn der Schichtgraph G_f^L hat höchstens m Kanten). Weil der Schichtgraph 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 \mathcal{O}(n m) 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 n-mal durchgeführt, alle ZURÜCK-Operationen zusammen haben eine Laufzeit von \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 m = | E(G) | und n = | V(G) | . Der Algorithmus von Dinic benötigt höchstens n − 1 Durchläufe. Der Schichtgraph G_f^L kann mit Breitensuche in Laufzeit \mathcal{O}(m) berechnet werden. Ein Sperrfluss in G_f^L kann mit der oben angegebenen Methode in Laufzeit \mathcal{O}(n m) berechnet werden. Damit ergibt sich eine Gesamtlaufzeit von \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 \mathcal{O}(n^3 + nm) erreichen.

Quellen

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Algorithmus von Ford und Fulkerson — Der Algorithmus von Ford und Fulkerson (nach seinen Erfindern Lester Randolph Ford junior und Delbert Ray Fulkerson[1]) dient der Berechnung eines maximalen s t Flusses in einem Netzwerk. Er sucht sukzessiv nach flussvergrößernden Pfaden im… …   Deutsch Wikipedia

  • Algorithmus von Edmonds und Karp — Der Edmonds Karp Algorithmus ist in der Informatik und der Graphentheorie eine Implementierung der Ford Fulkerson Methode zur Berechnung des maximalen s t Flusses in Netzwerken mit positiven reellen Kapazitäten. Sie verwendet den jeweils… …   Deutsch Wikipedia

  • Ford-Fulkerson-Algorithmus — Der Algorithmus von Ford und Fulkerson (nach seinen Erfindern Lester Randolph Ford junior und Delbert Ray Fulkerson[1]) dient der Berechnung eines maximalen Flusses in einem Netzwerk. Er sucht sukzessive nach flussvergrößernden Pfaden, vergrößert …   Deutsch Wikipedia

  • Satz von Hall — Eine Paarung (Matching) ist in der Graphentheorie eine Teilmenge der Kanten eines Graphen, in der keine zwei Kanten einen gemeinsamen Knoten besitzen. Paarungen haben innerhalb der Graphentheorie einen weiten Anwendungsbereich. Inhaltsverzeichnis …   Deutsch Wikipedia

  • Liste von Algorithmen — Dies ist eine Liste von Artikeln zu Algorithmen in der deutschsprachigen Wikipedia. Siehe auch unter Datenstruktur für eine Liste von Datenstrukturen. Inhaltsverzeichnis 1 Klassen von Algorithmen nach Komplexität 2 Klassen von Algorithmen nach… …   Deutsch Wikipedia

  • Edmonds-Karp-Algorithmus — Der Edmonds Karp Algorithmus ist in der Informatik und der Graphentheorie eine Implementierung der Ford Fulkerson Methode zur Berechnung des maximalen Flusses in Netzwerken. Sie verwendet den jeweils kürzesten augmentierenden Pfad in jedem… …   Deutsch Wikipedia

  • Flüsse und Schnitte in Netzwerken — sind Strukturen der Graphentheorie, die vielfältige Anwendungen finden. Inhaltsverzeichnis 1 Definitionen, wichtige Begriffe und Eigenschaften 1.1 Netzwerk 1.2 Fluss 1.2.1 …   Deutsch Wikipedia

  • Alternierender Pfad — Eine Paarung (Matching) ist in der Graphentheorie eine Teilmenge der Kanten eines Graphen, in der keine zwei Kanten einen gemeinsamen Knoten besitzen. Paarungen haben innerhalb der Graphentheorie einen weiten Anwendungsbereich. Inhaltsverzeichnis …   Deutsch Wikipedia

  • Augmentierender Pfad — Eine Paarung (Matching) ist in der Graphentheorie eine Teilmenge der Kanten eines Graphen, in der keine zwei Kanten einen gemeinsamen Knoten besitzen. Paarungen haben innerhalb der Graphentheorie einen weiten Anwendungsbereich. Inhaltsverzeichnis …   Deutsch Wikipedia

  • Größte Paarung — Eine Paarung (Matching) ist in der Graphentheorie eine Teilmenge der Kanten eines Graphen, in der keine zwei Kanten einen gemeinsamen Knoten besitzen. Paarungen haben innerhalb der Graphentheorie einen weiten Anwendungsbereich. Inhaltsverzeichnis …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”