Interaktiv · Network Flows
Max-Flow / Min-Cut
Der Edmonds-Karp-Algorithmus, Schritt für Schritt: In jeder Iteration wird per Breitensuche ein kürzester augmentierender Weg von der Quelle zur Senke gesucht, sein Engpass bestimmt und der Fluss entlang des Weges erhöht. Gesucht wird dabei nicht im Netzwerk selbst, sondern im Residualgraphen G_f, der als zweites Bild mitläuft und nach jeder Änderung neu gezeichnet wird. Der Pseudocode rechts zeigt an, in welcher Zeile der Algorithmus gerade steht. Bricht die Suche ab, liefert die noch erreichbare Knotenmenge direkt den minimalen Schnitt.
Pseudocode
- EDMONDS-KARP(G, c, s, t)
- 1für jede Kante e: f(e) ← 0
- 2wiederhole
- 3G_f ← Residualgraph zu f
- 4P ← kürzester s-t-Weg in G_f (BFS)
- 5falls P nicht existiert: brich ab
- 6Δ ← min{ c_f(e) : e ∈ P }
- 7erhöhe f entlang P um Δ
- 8S ← { v : v von s aus in G_f erreichbar }
- 9gib f und den Schnitt (S, V∖S) zurück
- Iteration
- –
- Δ
- –
- |f|
- 0
- Weg P
- –
Initialisierung
Jede Kante startet mit Fluss 0. Oben steht f/c für den aktuellen Fluss und die Kapazität. Darunter läuft der Residualgraph G_f mit: Jede Kante e mit freier Restkapazität c_f(e) = c(e) − f(e) erscheint dort als Vorwärtskante, jede Kante mit f(e) > 0 zusätzlich als gestrichelte Rückwärtskante mit Kapazität f(e). Beim Nullfluss ist G_f deshalb noch identisch mit dem Netzwerk.
Die Theorie dazu (Definitionen, das Max-Flow-Min-Cut-Theorem und die Algorithmen) steht in der Serie Network Flows.