Ford-Fulkerson-Algorithmus
Ford-Fulkerson-Algorithmus Definition
Der Ford-Fulkerson-Algorithmus findet die Lösung für folgende Aufgabe:
Ausgangspunkt
Man hat einen Graphen bzw. ein Netzwerk, zum Beispiel ein verzweigtes Rohrleitungssystem für Öl.
Es gibt eine Quelle (von dort kommt das Öl), eine Senke (dorthin soll das Öl) und verschiedene Stationen (Knoten in der Graphentheorie), die mittels Rohrleitungen (Kanten in der Graphentheorie) unterschiedlicher Kapazität (etwa gemessen in Liter pro Zeiteinheit) verbunden sind.
Frage / Problem
Wie / auf welchen Wegen kann ein maximaler Durchfluss von der Quelle zur Senke erreicht werden?
Dabei wird auch erlaubt, Kanten bzw. Pfade umgekehrt zu betrachten; das heißt, der Durchfluss wird dann reduziert (und kann später wieder erhöht werden).
Alternative Begriffe: Algorithmus von Ford und Fulkerson.
Beispiel
Beispiel: Ford-Fulkerson-Algorithmus
Ein Rohrleitungsnetzwerk umfasst die Quelle Q, die Senke S und dazwischen die Knoten A und B, in Summe also 4 Knoten.
Die Knoten sind durch folgende Kanten / Rohrleitungen mit den angegebenen Kapazitäten verbunden (Kapazitäten zum Beispiel Liter pro Minute):
Q – A: 5
Q – B: 4
A – B: 1
A – S: 2
B – S: 7
Über welche Pfade kann ein maximaler Durchfluss von Q nach S erreicht werden?
Der Ford-Fulkerson-Algorithmus löst das in mehreren Iterationen (Durchgängen) so:
Beginn
Man setzt zu Beginn den Durchfluss durch alle Kanten / Rohre auf 0.
1. Iteration
Anschließend beginnt man mit einem beliebigen Pfad von der Quelle bis zur Senke, beispielsweise: Q - A - S.
Der Engpass auf dem Weg ist die Kante A - S mit einer maximalen Kapazität von 2. Deshalb können von Q aus nur 2 losgeschickt werden.
Nun werden die auf diesem Pfad verbrauchten Kapazitäten auf den Kanten notiert:
Q – A: 2 / 5 (2 von 5 ausgelastet)
A – S: 2 / 2 (2 von 2, also voll ausgelastet)
2. Iteration
Einen weiteren Pfad von der Quelle bis zur Senke finden, zum Beispiel Q - B- S.
Der Engpass auf dem Weg ist die Kante Q - B mit einer maximalen Kapazität von 4. Deshalb können von Q aus nur 4 losgeschickt werden.
Nun werden wieder die auf diesem Pfad verbrauchten Kapazitäten auf den Kanten notiert:
Q – B: 4 / 4 (4 von 4, also voll ausgelastet)
B – S: 4 / 7 (4 von 7 ausgelastet)
3. Iteration
Einen weiteren Pfad von der Quelle bis zur Senke finden, zum Beispiel Q - A - B - S.
Der Engpass auf dem Weg ist die Kante A - B mit einer maximalen Kapazität von 1. Deshalb können von Q aus über diesen Pfad nur 1 zusätzlich losgeschickt werden.
Nun werden die auf diesem Pfad verbrauchten Kapazitäten auf den Kanten hinzuaddiert:
Q – A: 3 / 5 (3 von 5 ausgelastet)
A – B: 1 / 1 (1 von 1, also voll ausgelastet)
B – S: 5 / 7 (5 von 7 ausgelastet)
Ende
Es gibt keine weiteren Pfade mehr, die den Fluss erhöhen könnten, der Algorithmus endet.
Der maximale Fluss durch das Rohrleitungsnetzwerk ist: 2 + 4 + 1 = 7.
Verwendete Pfade (und Kapazitäten) Q - A - S (2), Q - B- S (4) und Q - A - B - S (1).