Der Goldberg-Tarjan-Algorithmus, auch Push-Relabel-Algorithmus genannt, ist ein Algorithmus aus der Graphentheorie zur Berechnung eines maximalen Flusses in einem Netzwerk. Er wurde von Andrew Goldberg und Robert Endre Tarjan entwickelt und 1988 publiziert.[1]

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  ,   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 wie 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

Bearbeiten

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 sich auch Laufzeiten von

 

und

 

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

Einzelnachweise

Bearbeiten
  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 Korte, Jens Vygen: Combinatorial Optimization. 3. Auflage. 2006, S. 168.