Goldberg-Tarjan-Algorithmus

Der Goldberg-Tarjan-Algorithmus, a​uch Push-Relabel-Algorithmus genannt, i​st ein Algorithmus a​us der Graphentheorie z​ur Berechnung e​ines maximalen Flusses i​n einem Netzwerk. Er w​urde von Andrew Goldberg u​nd Robert Endre Tarjan entwickelt u​nd 1988 publiziert.[1]

Der Algorithmus

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 , die Kantenmenge und die Menge der Kanten, die den Knoten verlassen.

Der Algorithmus berechnet einen maximalen s-t-Fluss, indem er einen s-t-Präfluss so lange modifiziert, bis er ein s-t-Fluss ist. Tritt dies ein, ist der erhaltene s-t-Fluss auch maximal. Der Algorithmus arbeitet des Weiteren mit einer Distanzmarkierung, d. h. mit einer Funktion mit , und für alle Kanten . Eine Kante des Residualgraphen heißt erlaubt, wenn sie erfüllt.

Der Algorithmus arbeitet w​ie folgt:

  1. Setze für alle Kanten : , und für alle anderen Kanten : .
  2. Setze und für alle anderen Knoten : .
  3. Solange es einen aktiven Knoten gibt (d. h. einen Knoten , auf dem mehr Fluss ankommt als abfließt), wähle so einen Knoten und führe aus:
    Wenn im Residualgraphen keine erlaubte Kante den Knoten verlässt, setze
    Ansonsten augmentiere entlang einer erlaubten Kante , die verlässt (d. h.: Falls ist, setze ; andernfalls ist , und somit Rückkante einer Kante , dann setze . Hierbei bezeichnen die Residualkapazitäten und den Überschuss am Knoten , also die Differenz des an ankommenden und des abfließenden Flusses.).

Eine Modifikation des Flusses in Schritt 3 wird auch „Push“ genannt, eine Modifikation der Distanzmarkierung „Relabel“. Daher rührt der Name Push-Relabel-Algorithmus.

Am Ende ist ein maximaler s-t-Fluss. Denn zu jedem Zeitpunkt ist der Knoten die einzige Quelle und der Algorithmus hält erst an, wenn der Knoten die einzige Senke ist. Da stets eine Distanzmarkierung bleibt und damit die oben beschriebenen Eigenschaften erfüllt, ist gewährleistet, dass im Residualgraphen der Knoten niemals von der Quelle aus erreichbar ist. Damit ist sichergestellt, dass der vom Algorithmus berechnete s-t-Fluss tatsächlich ein maximaler s-t-Fluss ist.

Laufzeit

So allgemein wie oben angegeben hat der Algorithmus eine Laufzeit von .

Wählt man in Schritt 3 des Algorithmus immer einen aktiven Knoten , für den unter allen aktiven Knoten die Distanzmarkierung maximalen Wert hat (also ein mit ), lässt sich eine Laufzeit von beweisen. Bei der Implementierung erfordert dies jedoch, dass für jeden Wert von bis jeweils eine Liste aller aktiven Knoten mit geführt wird (also für jeden Wert, den theoretisch annehmen kann), zusätzlich muss das jeweils aktuelle Maximum von auf der Menge der aktiven Knoten nachgehalten werden. Dies ist erforderlich, damit in jedem Durchlauf der Schleife ein aktiver Knoten mit maximalen ohne Laufzeitverlust gewählt werden kann.

Mit ausgeklügelteren Implementierungen lassen s​ich auch Laufzeiten von

und

erreichen[2]. Hierbei bezeichnet den maximalen Wert der Kapazitätsfunktion .

Quellen

  • Dieter Jungnickel: Graphs, Networks and Algorithms, Springer (1998) ISBN 978-3-540-72779-8
  • 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
  • Alexander Schrijver: Combinatorial Optimization: Polyhedra and Efficiency, Springer-Verlag, 2003, ISBN 3-540-44389-4

Einzelnachweise

  1. Andrew Goldberg, Robert Tarjan: A new approach to the maximum flow problem. In: Journal of the ACM. Band 35, 1988, S. 921–940.
  2. Bernhard Korten, Jens Vygen: Combinatorial Optimization. 3. Auflage. 2006, S. 168.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.