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:

def 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. Dafür garnieren wir den Code mit ein wenig redundanter Buchhaltung. Für einen Fluss $f$ bezeichnen wir mit $G_f$ den Digraphen des Residualnetzwerks, d.h. den Graphen $G = (V,E_f)$ mit $E_f = \{ (u,v) \in V \times V \ | \ c(u,v) - f(u,v) \gt 0\}$.

def EdmondsKarpWithTwoLoops (G= (V,E), c, s, t):
  f = 0 # der Fluss, der überall 0 ist
  d = dist(s,t, G) 
  while (d < infinity):
      # for bookkeeping reasons only:
      # compute dist(s,v,G_f) for all v
      # let L_i := {v | dist(s,v,G_f) = i}
      # s is in L_0 and t is in L_d
      while (residual network G_f has a path from s to t of length d):
          let p be a shortest path from s to t
          f = f + f_p
      d = dist(s,t, G_f)
  return f

Beweis. Betrachten wir Zeile 7 und das Residualnetzwerk $(V,s,t,c-f)$ bzw. den dadurch definierten Digraphen $G_f = (V,E_f)$. Es gibt also in $G_f$ einen $s$-$t$-Pfad mit $d$ Kanten, aber keinen kürzeren. Jeder Knoten gehört einer der Mengen $L_0, L_1, \dots, L_{n-1}, L_{\infty}$ an; letztere sind die Knoten $v$ mit $\dist(s,v,G_f) = \infty$, die also von $s$ aus nicht erreichbar sind. Wir schreiben $\vec{L} := (L_0, L_1, \dots, L_{n-1}, L_{\infty})$ für die Folge dieser Mengen. Sei $(u,v)$ eine Kante mit $u \in L_i$ und $v \in L_j$. Dann gilt $\dist(u,v,G_f) \leq i+1$ und somit $j \leq i+1$. Wir bezeichnen $(u,v)$ als Vorwärtskante wenn $j = i+1$, Rückwärtskante wenn $j \lt i$ und Querkante wenn $j = i$ gilt. Formal:

\begin{align*} \forward(G_f, \vec{L} ) := \{ (u,v) \in E_f \ | \ \exists 0 \leq i \leq n-2: u \in L_{i}, v \in L_{i+1} \} \ , \end{align*}

Wenn \(p\) ein Pfad von \(s\) nach \(t\) in \(G_f\) mit $d$ Kanten ist, dann 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. Wenn nun $f_p$ der Fluss entlang eines Pfades von Länge $d$ ist, und $(u,v)$ eine Kante von $p$ mit kleinster Restkapazität $c(u,v) - f(u,v)$ ist, dann wird diese Kante im neuen Fluss $f' = f+f_p$ ausgelastet sein, und nicht mehr Teil von $G_{f'}$ sein. Wenn wir von $G_f$ zu $G_{f'}$ übergehen, geht also $(u,v)$ verloren; es kommen womöglich neue Kanten hinzu, die aber sind alle von der Form $(y,x)$ für eine Kante $(x,y) \in p$. Es sind also Rückwärtskanten, die von einem $L_i$ zu $L_{i-1}$ führen. Wir halten fest: die Anzahl der Vorwärtskanten in $G_{f'}$ ist kleiner als die in $G_f$:

\begin{align*} \forward(G_{f + f_p}, \vec{L}) & \subseteq \forward(G_{f}, \vec{L}) \\ |\forward(G_{f + f_p}, \vec{L})| & \lt |\forward(G_{f}, \vec{L})| \ . \end{align*}

Hier ist ein Beispiel für eine Augmentierung entlang eines "schwarzen" Pfades aus Vorwärtskanten. Alle neu entstehenden Kanten sind grau.

Wie groß kann $\forward(G_f, \vec{L})$ am Anfang, also in Zeile 7 sein? $G$ hat $m$ Kanten; im Residualnetzwerk $G_f$ kommen womöglich für jede Kante $(u,v)$ die Gegenkanten $(v,u)$ hinzu. $G_f$ hat also maximal $2m$ Kanten. In Bezug auf $\vec{L}$ kann von $(u,v)$ und $(v,u)$ jedoch maximal eine eine Vorwärtskante sein. Somit gibt es maximal $m$ Vorwärtskanten. Mit jeder Iteration der inneren while-Schleife verschwindet mindestens eine und es kommt keine hinzu; nach maximal $m$ Durchläufen gibt es keine Vorwärtskanten mehr und daher in $G_f$ auch keinen Pfad der Länge $d$ mehr.

Die innere while-Schleife endet also nach maximal $m$ Schritten. Wenn sie endet, gibt es in $G_f$ keinen $s$-$t$-Pfad der Länge $d$ mehr, aber auch keinen kürzeren: jede Kante ist ja immer noch eine Vorwärtskante, eine Rückwärtskante oder eine Querkante, und daher kann ein $s$-$t$-Pfad pro Kante höchstens in das nächsthöhere Level $L_i$ gehen, aber keines überspringen. Daraus folgt, dass die äußere Schleife maximal $n-1$ mal durchlaufen wird: anfangs gilt $d \geq 1$; in jedem Durchlauf steigt $d$ um mindestens $1$; nach $n-1$ Durchläufen gilt also $d \geq n$ und somit $d = \infty$ (wenn es keinen Pfad von $n-1$ oder weniger Kanten gibt, dann gibt es gar keinen). \(\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.

Der Algorithmus von Dinic

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:

def 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.

def 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.:

Laufzeitanalyse

Wie schon beim Edmonds-Karp-Algorithmus kann die äußere Schleife von Dinic maximal $n-1$ mal durchlaufen werden, weil die Länge eines kürzesten $s$-$t$-Pfades in $G_f$ mit jeder Iteration um mindestens 1 ansteigt. Die innere Schleife (Zeile 5) führt insgesamt maximal $m$ Durchläufe aus, da die Menge $F$ in jeder Iteration mindestens eine Kante verliert: die mit kleinster Kapazität auf dem Pfad $p$, weil die dann ausgelastet ist. Untersuchen wir also die Laufzeit des $i$-ten Aufrufs von destructiveDepthFirstSearch. Jede Kante, die destructiveDepthFirstSearch besucht, kommt entweder in den Pfad (Zeile 19), was höchstens $n-1$ mal passiert, oder sie wird gelöscht (21). Sei $d_i$ die Anzahl der Kanten, die im $i$-ten Aufruf gelöscht werden. Die Laufzeit von des $i$-ten Aufrufs von destructiveDepthFirstSearch ist also proportional zu $n + d_i$. Die Laufzeit aller $t \leq m$ Aufrufe ist dann proportional zu höchstens

wobei $ \sum_{i=1} d_i \leq m$ gilt weil jede Kante nur einmal gelöscht werden wird. Die Laufzeit aller (höchstens $m$) Aufrufe von destructiveDepthFirstSearch ist also $O(mn)$. Die äußere Schleife wird maximal $n-1$ durchlaufen, und somit gilt:

Material

• Meine Folien zu Dinic' Algorithmus. Insbesondere der Teil über Unit Capacity Networks ist relevant, weil ich den noch nicht in das Vorlesungsskipt eingearbeitet habe.