Ford-Fulkerson, kürzester augmentierender Pfad (Algorithmus 6.3)

So geht’s: Beim Öffnen läuft tinyFN.txt mit dem Code, wie er im Buch steht. Links ist das Flussnetzwerk, an jeder Kante Fluss/Kapazität, rot sind Kanten mit Fluss. Rechts ist das Restnetzwerk. Graue Pfeile sind Vorwärtskanten mit der Restkapazität, rote Pfeile Rückwärtskanten mit dem Fluss, den man zurücknehmen kann. Jede Runde ist eine Breitensuche: Der orange Knoten wird gerade bearbeitet, die orange Kante gerade geprüft, markierte Knoten sind hellblau und edgeTo[] blau. Erreicht die Suche t, wird der augmentierende Pfad blau, und der Engpass fließt dazu. Am Ende sind die markierten Knoten grün, das ist die s-Seite des minimalen Schnitts. „wie Abbildung 6.22“ stellt die Adjazenzlisten auf Einfügereihenfolge um, dann kommen genau die drei Pfade aus der Abbildung heraus (siehe Anmerkung). „Beispiel der Instanz“ ist das kleine Netz aus dem Text, „Zufallsnetz“ ein zufälliges.

Erklärung

Ford-Fulkerson, kürzester augmentierender Pfad (Algorithmus 6.3), Klasse FordFulkerson. Kapitel 6, Abschnitt Netzwerkfluss. Mit dem kürzesten Pfad heißt die Variante auch Edmonds-Karp (1972).

Das Problem: maximaler Fluss

• Ein Flussnetzwerk ist ein gerichteter Graph, in dem jede Kante eine Kapazität hat: wie viel höchstens durchfließen kann, z. B. Wasser, Öl, Datenrate oder Waren.
• Es gibt eine Quelle s und eine Senke t.
• Ein Fluss muss zwei Regeln einhalten:
  • Kapazität: Auf keiner Kante fließt mehr als ihre Kapazität.
  • Erhaltung: In jeden Knoten außer s und t fließt genauso viel hinein wie heraus.
• Gesucht ist der Fluss, bei dem möglichst viel von s nach t kommt.

Restnetzwerk (Residualgraph): Das Herzstück des Verfahrens. Zu jeder Kante v→w mit Fluss f und Kapazität c gibt es zwei Möglichkeiten:

• Vorwärts v→w: Es passt noch c − f dazu.
• Rückwärts w→v: Es lassen sich bis zu f wieder zurücknehmen.
• Die Rückwärtskanten sind entscheidend. Durch sie kann der Algorithmus eine früher getroffene ungünstige Wahl wieder korrigieren.
• FlowEdge regelt das intern:
  • residualCapacityTo(v): Ist v das Ziel der Kante, liefert sie c − f (vorwärts). Ist v der Startpunkt, liefert sie f (rückwärts).
  • addResidualFlowTo(v, delta): Je nach Richtung wird der Fluss erhöht oder verringert.

Augmentierender Pfad: Ein Weg von s nach t im Restnetzwerk, auf dem jede Kante Restkapazität > 0 hat. Gibt es einen, lässt sich der Fluss erhöhen.

Der Code:

• Solange hasAugmentingPath(G, s, t) einen Pfad findet:
  • Engpass berechnen: über edgeTo von t zurück bis s laufen und die kleinste Restkapazität auf dem Weg bestimmen (bottle).
  • Augmentieren: auf demselben Weg zurück, auf jeder Kante addResidualFlowTo(v, bottle).
  • value += bottle.
• hasAugmentingPath (Listing 6.12, im Hintergrund durchscheinend) ist die Breitensuche aus Algorithmus 4.2 [31] mit marked[], edgeTo[] und Warteschlange [16]. Einziger Unterschied: Eine Kante zählt nur, wenn ihre Restkapazität in diese Richtung größer als 0 ist. Weil es eine Breitensuche ist, wird immer der Pfad mit den wenigsten Kanten genommen.
• inCut(v): marked[v] nach der letzten, erfolglosen Suche. Siehe Schnitt unten.
• Der Testclient gibt alle Kanten mit Fluss > 0 und den Gesamtwert aus.

Warum Rückwärtskanten nötig sind (eigenes Beispiel): s = 0, t = 3, Kanten 0→1, 0→2, 1→2, 1→3, 2→3, alle mit Kapazität 1.

• Angenommen, man nimmt zuerst den Pfad 0→1→2→3 (Fluss 1). Danach sind 0→1 und 2→3 voll, und vorwärts geht scheinbar nichts mehr.
• Im Restnetzwerk gibt es aber die Rückwärtskante 2→1. Pfad 0→2→1→3 bringt noch einmal 1: Der Fluss über 1→2 wird dabei zurückgenommen und umgeleitet.
• Ergebnis 2, das Maximum. Ohne Rückwärtskanten wäre man bei 1 stecken geblieben.
• Die Breitensuche hätte hier übrigens gleich die kurzen Pfade 0→1→3 und 0→2→3 genommen. Im Allgemeinen ist das Zurücknehmen trotzdem unverzichtbar.

Max-Flow-Min-Cut-Theorem:

• Ein s-t-Schnitt teilt die Knoten in eine Seite mit s und eine mit t. Seine Kapazität ist die Summe der Kapazitäten aller Kanten von der s-Seite zur t-Seite.
• Kein Fluss kann größer sein als irgendein Schnitt, denn alles muss irgendwo über den Schnitt.
• Das Theorem sagt: Der maximale Fluss ist gleich dem minimalen Schnitt. Gleichbedeutend: Ein Fluss ist genau dann maximal, wenn es keinen augmentierenden Pfad mehr gibt.
• Den minimalen Schnitt bekommt man gratis: Nach der letzten Breitensuche bilden die markierten Knoten (inCut) die s-Seite.

Kosten:

• Mit kürzesten augmentierenden Pfaden gibt es höchstens E · V / 2 Augmentierungen. Jede kostet eine Breitensuche (E + V), insgesamt im schlimmsten Fall also etwa V · E².
• In der Praxis ist es meist viel schneller, weil weit weniger Pfade gebraucht werden.
• Ohne die Regel „kürzester Pfad“ kann Ford-Fulkerson bei ungünstiger Pfadwahl extrem viele Augmentierungen brauchen, bei irrationalen Kapazitäten sogar nie enden. Genau deshalb die Breitensuche.

Anwendungen: Transport- und Versorgungsnetze, Datennetze, Bildsegmentierung (minimaler Schnitt trennt Vordergrund und Hintergrund) und vor allem als Werkzeug für andere Probleme. Das beste Beispiel ist das bipartite Matching, etwa Bewerber auf Stellen verteilen: Quelle an alle Bewerber, alle Stellen an die Senke, alle Kapazitäten 1, und der maximale Fluss ist die größte Zuordnung. Genau dieses „Problem A auf Problem B zurückführen“ ist das Thema des folgenden Abschnitts über Reduktion.

Bezüge: Breitensuche [31], Warteschlange [16], edgeTo-Pfadrückverfolgung wie in [30] und [39]. Die Schnitteigenschaft der MSTs [37] ist ein entfernter Verwandter des Schnittbegriffs hier.

Kapitel 6:

• Algorithmus 6.1: B-Baum [54]
• Algorithmus 6.2: Suffixarray [55]
• Algorithmus 6.3: Ford-Fulkerson (Max-Fluss) [56]