8.3 Effiziente Algorithmen für Max Flow: Edmons-Karp und Dinic
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
EdmondsKarp
zu bestimmen,
müssen wir herausfinden, wie oft im Schlimmsten Fall die
while
-Schleife
durchlaufen
werden kann.
while
-Schleife in
Edmonds-Karp
wird
höchstens EdmondsKarp
ist.
Wir betrachten nun in
Überzeugen Sie sich, dass die kürzesten Pfade von
while
-Schleife von
EdmondsKarp
geschieht
mindestens eine der beiden folgenden Möglichkeiten:
wächst;- die Anzahl der Vorwärtskanten in
sinkt.
Das ursprüngliche Netzwerk
while
-Schleife
terminiert. Möglichkeit
1 kann höchstens
Wir müssen allerdings noch das Lemma beweisen.
while
-Schleife
auf keinen Fall abnehmen; in anderen Worten Wenn
nun
Beachten Sie, dass die Begriffe der Vorwärtskanten und des Abstandsmaßes
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
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
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.:
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.