TI

Im letzten Teilkapitel haben wir erwähnt, dass der Ford-Fulkerson-Algorithmus in Extremfällen nur langsam oder sogar gar nicht zu einer optimalen Lösung konvergiert. Glücklicherweise lässt sich dieser Makel mit einer kleinen Änderung des Codes leicht beheben. Wir erhalten den Edmonds-Karp-Algorithmus:

EdmondsKarp (G, c, s, t):
f = 0 // der Fluss, der überal 0 ist
while (residual network G_f has a path from s to t ):
  let p be a shortest path from s to t
  f = f + f_p
return f

Der Trick ist also: wähle immer einen kürzesten Pfad zum Augmentieren, also einen mit der kleinsten Anzahl von Kanten. Wir wissen bereits, wie wir einen solchen finden: in $O(n+m)$ Zeit mit Breitensuche. Um die Laufzeit von EdmondsKarp zu bestimmen, müssen wir herausfinden, wie oft im Schlimmsten Fall die while-Schleife durchlaufen werden kann.

Theorem Die while-Schleife in Edmonds-Karp wird höchstens $nm$ mal durchlaufen. Die Laufzeit ist daher $O(nm^2)$.

Beweis. Der Beweis ist nicht ganz einfach. Wir müssen ein wenig Notation einführen. Wenn $G$ ein Digraph ist und $u,v$ zwei Knoten, dann bezeichnen wir mit $\dist(u,v,G)$ die Länge des kürzesten (gerichteten) Pfades von $u$ nach $v$. Mit Länge meinen wir hier einfach nur die Anzahl der Kanten; wir sprechen nicht über Kantenkosten. Falls es gar keinen Pfad gibt, definieren wir $\dist(u,v,G) = \infty$. Wenn $G = (V,c,s,t)$ ein Flussnetzwerk ist, dann definiert das ja einen gerichteten Graphen mittels $$ E(G) := \{ (u,v) \in V \times V \ | \ c(u,v) > 0 \} \ . $$ Die Notation $\dist(u,v,G)$ macht also auch dann Sinn, wenn $G$ ein Flussnetzwerk ist. (Erinnerin Sie sich an die beiden Definitionen von Flussnetzwerken: die mit einem expliziten zugrunde liegenden Digraph $G = (V,E)$ und die andere, in der alle Informationen in der Funktion $c: V \times V \rightarrow \R^+_0$ stecken.) Wir werden im Laufe des Beweises auch von $\dist(u,v,G_f)$ sprechen, wobei dann $G_f$ das Residualnetzwerk in Zeile 4 von EdmondsKarp ist.

Wir betrachten nun in $G_f$ all jene Kanten $(u,v) \in E(G_f) $, die auf einem kürzesten Pfad von $s$ nach $v$ liegen. Eine solche Kante nennen wir Vorwärtskante. Die Kante $(u,v)$ ist eine Vorwärtskante genau dann, wenn $ \dist(s,v) = \dist(s,u) + 1$ gilt. Wenn $p$ ein kürzester Pfad von $s$ nach $t$ in $G_f$ ist, so sind alle Kanten in $p$ auch Vorwärtskanten. Hier ist als Beispiel das Netzwerk $G$, dem wir bereits oben begegnet sind. Ich habe neben jeden Knoten $u$ die Zahl $\dist(u,v,G)$ geschrieben; Vorwärtskanten sind schwarz, alle anderen sind grau.

Überzeugen Sie sich, dass die kürzesten Pfade von $s$ nach $t$ genau die sind, die ausschließlich schwarze Kanten verwenden.

Lemma In jedem Durchlauf der while-Schleife von EdmondsKarp geschieht mindestens eine der beiden folgenden Möglichkeiten:

$\dist(s,t,G_f)$ wächst;
die Anzahl der Vorwärtskanten in $G_f$ sinkt.

Das ursprüngliche Netzwerk $G$ hat $m$ Kanten. Für jede Kante $(u,v)$ könnte im Laufe des Algorithmus eine "Gegenkante" $(v,u)$ entstehen; allerdings kann von diesem Zwillingspaar höchstens eine eine Vorwärtskante in $G_f$ sein; also hat es $G_f$ höchstens $m$ Vorwärtskanten. Das heißt, dass Möglichkeit 2 höchstens $m$ mal hintereinander geschehen kann; danach muss entweder Möglichkeit 1 geschehen, oder die while-Schleife terminiert. Möglichkeit 1 kann höchstens $n-1$ mal geschehen: anfangs haben wir $\dist(s,t,G) \geq 1$, und solange es überhaupt einen Pfad gibt, hat dieser Länge höchstens $n-1$. Danach kann $\dist(s,t,G_f)$ nur noch auf $\infty$ springen und die Schleife terminiert. Dies zeigt, dass es höchstens $m (n-1) \leq mn$ Schleifendurchläufe gibt und beweist das Theorem. $\square$

Wir müssen allerdings noch das Lemma beweisen.

Beweis des Lemmas. Was geschieht denn, wenn wir den Fluss augmentieren? Sei $G_i$ das aktuelle Flussnetzwerk in Zeile 4 und $G_{i+1}$ das Flussnetzwerk im nächsten Durchlauf. Sei $d_i := \dist(u,v,G_i)$ und $d_{i+1} := \dist(u,v,G_{i+1})$. Wir erhalten $G_{i+1}$ aus $G_i$, indem wir entlang des Pfades $f_p$ augmentieren. Die einzigen Kanten, die in G_{i+1} hinzukommen, sind also die "Rückwärtskanten" $(v,u)$ für jede Kante $(u,v) \in p$. Diese Kanten gehen in die "falsche" Richtung und können nicht Teil eines Pfades des Länge $d_i$ von $s$ nach $t$ sein, schon gar nicht eines kürzeren. Wir sehen also: die Länge des kürzesten Pfades von $s$ nach $t$ kann in einem Durchlauf der while-Schleife auf keinen Fall abnehmen; in anderen Worten $d_{i} \leq d_{i+1}$. Hier ist ein Beispiel für eine Augmentierung entlang eines "schwarzen" Pfades aus Vorwärtskanten. Alle neu entstehenden Kanten sind grau.

Wenn nun $d_i \lt d_{i+1}$ gilt, dann ist Möglichkeit 1 eingetreten und der Beweis ist fertig. Ansonsten gilt $d_i=d_{i+1}$. Da alle neu eingefügten Kanten "Rückwärtskanten" sind, ist zumindest keine Vorwärtskante dazugekommen. Es ist aber mindestens eine Vorwärtskante weggefallen: nämlich jene Kante $e \in p$ mit $c(e)=c_{\min}$, deren Kapazität vom Fluss $f_p$ voll ausgeschöpft wird. Die Anzahl der Vorwärtskanten sinkt also, und Möglichkeit 2 ist eingetreten. $\square$

Beachten Sie, dass die Begriffe der Vorwärtskanten und des Abstandsmaßes $\dist(u,v,G_f)$ nur in der Analyse von EdmondsKarp vorkommen, im Algorithmus-Code selbst aber keinerlei Rolle spielen. Eine Idee, die doch recht hohe Laufzeit von Edmonds-Karp zu verbessern, ist, die Vorwärtskanten explizit im Algorithmus zu verwenden, z.B. nur entlang der schwarzen Kanten überhaupt nach kürzesten Pfaden zu suchen. Wenn man diese Idee konsequent umsetzt, erhält man den Dinic-Algorithmus.

Gegeben ein Residualnetzwerk $G_f$, sei $F$ die Menge an Vorwärtskanten in $G_f$. Die Kantenmenge $F$ kann z.B. mit Breitensuche in $O(n+m)$ Zeit ermittelt werden. Eine erste Beobachtung ist, dass jeder $s-t$-Pfad im Digraph $ (V,F)$ ein kürzester Pfad ist; wir können also einen solchen Pfad mittels Tiefensuche finden. Das ist gut, denn Tiefensuche ist irgendwie einfacher als Breitensuche. Die zweite Beobachtung ist, dass wir die Tiefensuche so implementieren können, dass sie "im Schnitt" nicht $O(n+m)$ sondern nur $O(n)$ Zeit braucht. Wenn der Graph "dicht" ist, also $m \gg n$ gilt, dann ist dies substantiell schneller. Hier ist der (recht informelle) Pseudo-Code von Dinic:

Dinic (G, c, s, t):
f = 0 // der Fluss, der überal 0 ist
while (true):
  let F be the set of forward edges in the residual network G_f
  while destructiveDepthFirstSearch(s,t,(V,F)) finds a path p:
    f = f + f_p
    update the capacities in F accordingly; don't add any "back edges" to F
  end while
  forget F and build the residual network G_f with back edges and all
end while
return f

Als nächstes beschreiben wir die Subroutine destructiveDepthFirstSearch. Die Idee ist, dass wir, beginnend von $s$, einfach drauflossuchen. Wenn wir zu $t$ gelangen, haben wir einen Pfad gefunden. Wenn wir an einem Knoten $v$ steckenbleiben, zum Beispiel, weil er keine ausgehenden Kanten hat, dann ist $v$ eine Sackgasse, und wir können ihn löschen. Der Punkt ist, dass $F$ nur aus Vorwärtskanten besteht, der Digraph $(V,F)$ somit azyklisch ist. Es kann also nie passieren, dass die Tiefensuche eine Kante $(u,v)$ erkundet und $v$ bereits auf dem Pfad von $s$ nach $u$ liegt.

destructiveDepthFirstSearch(u,t,(V,F)) // gibt einen Pfad von u nach t zurück oder "failure", falls es keinen gibt; löscht alle gefundenen Sackgassen                        
if u == t:
  return [t]
for v in outNeighbors(u):
  p = destructiveDepthFirstSearch(v,t,(V,F)) // p ist entweder ein Pfad von v nach t oder "failure"
  if (p is a path):
    return [u] + p // [u] + p ist nun ein Pfad von u nach t
  else // dann ist p == "failure" und es gibt keinen v-t-Pfad
    delete edge (u,v) from F
end for
// wenn wir in diese Code-Zeile kommen, dann gibt es keinen Pfad von u nach t
return "failure"

Hier ist eine Beispielausführung der Zeilen 4 bis 9 von Dinic, also eine Iteration der äußeren while-Schleife. Wir führen die Subroutine destructiveDepthFirstSearch mehrfach aus:

Wenn die innere while-Schleife terminiert, sammeln wir in Zeile 9 die gefundenen Flüsse und machen weiter wie normal, d.h. wir bilden das Residualnetzwerk etc.:

Übungsaufgabe Implementieren Sie Edmonds-Karp. Ich habe bereits eine Klasse FlowNetwork geschrieben, die von der Konsole ein Flussnetzwerk einlesen kann. Den Code finden Sie in 03-flow.zip.

Beispiele, um Ihren Algorithmus zu testen, finden Sie hier. Klicken Sie auf die jeweiligen Abbildungen, um an die Codierung des Graphen als Textdatei zu gelangen. Alle Textdateien sollten aber auch in 03-flow.zip unter data zu finden sein.