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 ${\displaystyle (G,u,s,t)}$ ${\displaystyle G}$ den gerichteten Graphen, ${\displaystyle u\colon E(G)\rightarrow \mathbb {R} _{+}}$ die Kapazitätsfunktion (wobei ${\displaystyle u(e)}$ die Kapazität einer Kante ${\displaystyle e}$ angibt), ${\displaystyle s}$ den Knoten, von dem der Fluss startet, und ${\displaystyle t}$ den Zielknoten des Flusses. ${\displaystyle V(G)}$ bezeichnet die Knotenmenge des Graphen ${\displaystyle G}$, ${\displaystyle E(G)}$ die Kantenmenge und ${\displaystyle \delta ^{+}(v)}$ die Menge der Kanten, die den Knoten ${\displaystyle v}$ verlassen.

Der Algorithmus berechnet einen maximalen s-t-Fluss, indem er einen s-t-Präfluss ${\displaystyle f}$ 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 ${\displaystyle \psi \colon V(G)\rightarrow \mathbb {N} _{0}}$ mit ${\displaystyle \psi (s)=|V(G)|}$, ${\displaystyle \psi (t)=0}$ und für alle Kanten ${\displaystyle e=(v,w)\in G_{f}:\ \psi (v)\leq \psi (w)+1}$. Eine Kante ${\displaystyle (v,w)\in E(G_{f})}$ des Residualgraphen ${\displaystyle G_{f}}$ heißt erlaubt, wenn sie ${\displaystyle \psi (v)=\psi (w)+1}$ erfüllt.

Der Algorithmus arbeitet w​ie folgt:

1. Setze für alle Kanten ${\displaystyle e\in \delta ^{+}(s)}$: ${\displaystyle f(e):=u(e)}$, und für alle anderen Kanten ${\displaystyle e}$: ${\displaystyle f(e):=0}$.
2. Setze ${\displaystyle \psi (s):=|V(G)|}$ und für alle anderen Knoten ${\displaystyle v}$: ${\displaystyle \psi (v):=0}$.
3. Solange es einen aktiven Knoten ${\displaystyle v\in V(G)}$ gibt (d. h. einen Knoten ${\displaystyle v\in V(G)\setminus \{s,t\}}$, auf dem mehr Fluss ankommt als abfließt), wähle so einen Knoten ${\displaystyle v}$ und führe aus:

   Wenn im Residualgraphen ${\displaystyle G_{f}}$ keine erlaubte Kante den Knoten ${\displaystyle v}$ verlässt, setze ${\displaystyle \psi (v):=\min\{\psi (w)+1\mid \exists e\in E(G_{f}):e=(v,w)\}}$

   Ansonsten augmentiere ${\displaystyle f}$ entlang einer erlaubten Kante ${\displaystyle e}$, die ${\displaystyle v}$ verlässt (d. h.: Falls ${\displaystyle e\in E(G)}$ ist, setze ${\displaystyle f(e):=f(e)+\min\{u_{f}(e),\operatorname {ex} (v)\}}$; andernfalls ist ${\displaystyle e\in E(G_{f})\setminus E(G)}$, und somit ${\displaystyle e={\overleftarrow {g}}}$ Rückkante einer Kante ${\displaystyle g\in E(G)}$, dann setze ${\displaystyle f(g):=f(g)-\min\{u_{f}(e),\operatorname {ex} (v)\}}$. Hierbei bezeichnen ${\displaystyle u_{f}}$ die Residualkapazitäten und ${\displaystyle \operatorname {ex} (v)}$ den Überschuss am Knoten ${\displaystyle v}$, also die Differenz des an ${\displaystyle v}$ ankommenden und des abfließenden Flusses.).

Eine Modifikation des Flusses ${\displaystyle f}$ in Schritt 3 wird auch „Push“ genannt, eine Modifikation der Distanzmarkierung ${\displaystyle \psi }$ „Relabel“. Daher rührt der Name Push-Relabel-Algorithmus.

Am Ende ist ${\displaystyle f}$ ein maximaler s-t-Fluss. Denn zu jedem Zeitpunkt ist der Knoten ${\displaystyle s}$ die einzige Quelle und der Algorithmus hält erst an, wenn der Knoten ${\displaystyle t}$ die einzige Senke ist. Da ${\displaystyle \psi }$ stets eine Distanzmarkierung bleibt und damit die oben beschriebenen Eigenschaften erfüllt, ist gewährleistet, dass im Residualgraphen ${\displaystyle G_{f}}$ der Knoten ${\displaystyle t}$ niemals von der Quelle ${\displaystyle s}$ 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 ${\displaystyle {\mathcal {O}}(|V(G)|^{2}\ |E(G)|)}$.

Wählt man in Schritt 3 des Algorithmus immer einen aktiven Knoten ${\displaystyle v}$, für den unter allen aktiven Knoten die Distanzmarkierung ${\displaystyle \psi }$ maximalen Wert hat (also ein ${\displaystyle v}$ mit ${\displaystyle \psi (v)=\max\{\psi (x)\mid x{\text{ ist aktiver Knoten}}\}}$), lässt sich eine Laufzeit von ${\displaystyle {\mathcal {O}}(|V(G)|^{2}{\sqrt {|E(G)|}})}$ beweisen. Bei der Implementierung erfordert dies jedoch, dass für jeden Wert ${\displaystyle i}$ von ${\displaystyle 0}$ bis ${\displaystyle 2{\mathopen {|}}V(G){\mathclose {|}}-2}$ jeweils eine Liste aller aktiven Knoten ${\displaystyle v}$ mit ${\displaystyle \psi (v)=i}$ geführt wird (also für jeden Wert, den ${\displaystyle \psi }$ theoretisch annehmen kann), zusätzlich muss das jeweils aktuelle Maximum von ${\displaystyle \psi }$ auf der Menge der aktiven Knoten nachgehalten werden. Dies ist erforderlich, damit in jedem Durchlauf der Schleife ein aktiver Knoten ${\displaystyle v}$ mit maximalen ${\displaystyle \psi (v)}$ ohne Laufzeitverlust gewählt werden kann.

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

${\displaystyle {\mathcal {O}}(|V(G)|\ |E(G)|\ \log _{2+{\frac {|E(G)|}{|V(G)|\log(|V(G)|)}}}(|V(G)|))}$

und

${\displaystyle {\mathcal {O}}(\min\{{\sqrt {|E(G)|}},{\sqrt[{3}]{|V(G)|^{2}}}\}\ |E(G)|\ \log \left({\frac {|V(G)|^{2}}{|E(G)|}}\right)\ \log(u_{\max }))}$

erreichen[2]. Hierbei bezeichnet ${\displaystyle u_{\max }}$ den maximalen Wert der Kapazitätsfunktion ${\displaystyle u}$.

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.