Kurs:Algorithmen und Datenstrukturen/Vorlesung/Flussproblem Ford-Fulkerson

Ford-Fulkerson

Auf dieser Seite wird der Ford Fulkerson Algorithmus zur Berechnung des maximalen Flusses behandelt.

Berechnung des maximalen Flusses

Der Ford-Fulkerson Algorithmus ist ein effizienter Algorithmus zur Bestimmung eines maximalen Flusses von q nach z. Dabei wird der Greedy Algorithmus mit Zufallsauswahlen gemischt. Hier wird das Prinzip "Füge so lange verfügbare Pfade zum Gesamtfluss hinzu wie möglich" verfolgt. Zuerst soll ein nutzbarere Pfad durch Tiefensuche gefunden werden. Für die Kanten werden dann drei Werte notiert. Zum einen der aktuellen Fluss entlang der Kante. Im initialisierten Graphen ist dieser Wert überall 0. Zudem wird die vorgegebene Kapazität c notiert und die abgeleitete noch verfügbare Restkapazität von c-f.

Algorithmus

initialisiere Graph mit leerem Fluss;
do
   wähle nutzbaren Pfad aus;
   füge Fluss des Pfades zum Gesamtfluss hinzu;
while noch nutzbarer Pfad verfügbar

Ein nutzbarere Pfad ist ein zyklenfreier Pfad von der Quelle q zum Ziel z, der an allen Kanten eine verfügbare Kapazität hat. Ein nutzbarer Fluss ist das Minimum der verfügbaren Kapazitäten der einzelnen Kanten.

Der nachfolgende Pseudocode realisiert das Problem mit zusätzlichen Rückkanten.

für jede Kante(u,v) füge Kante (v,u) mit Kapazität 0 ein;
initialisiere Graph mit leerem Fluss;
do
   wähle nutzbaren Pfad aus;
   füge Fluss des Pfades zum Gesamtfluss hinzu;
while noch nutzbarer Pfad verfügbar

Beispiele

FordFulkerson1

Wir haben einen Graph mit Kapazitäten gegeben

FordFulkerson2

Es wird mit dem Fluss 0 initialisiert. Notation: <aktueller Fluss f> / <Kapazität c> / <verfügbare Kapazität c-f>

FordFulkerson3

Die Auswahl der nutzbaren Pfade geschieht zufällig oder durch geeignete Heuristik. Es gibt auch kürzere Pfade mit höheren Kapazitäten. Die Rückkanten werden mit der Kapazität 0 eingefügt. Die Auswahl eines Pfades geschieht durch $1\to 2\to 4\to 5\to 6$ Der nutzbare Fluss beträgt 4.

FordFulkerson4

Der Fluss wird aktualisiert. Die Auswahl des Pfades ist nun : $1\to 3\to 5\to 6$. Der nutzbare Fluss beträgt 5.

Ford fulkerson5

Der Fluss wird aktualisiert. Die Auswahl des Pfades ist nun : $1\to 3\to 2\to 5\to 6$. Der nutzbare Fluss beträgt 3.

Ford fulkerso6

Der Fluss wird aktualisiert. Die Auswahl des Pfades ist nun : $1\to 3\to 2\to 5\to 4\to 6$. Der nutzbare Fluss beträgt 2.

Ford fulkerson7

An dieser Stelle sind keine Kapazitäten mehr über und die Berechnung wir beendet. Der maximale Fluss beträgt 14.

Der Algorithmus kann dabei auf verschiedene Ergebnisse kommen, jedoch ist der maximale Fluss immer gleich. Eine weitere Lösung ist folgende:

Zunächst wird der Pfad $1\to 2\to 5\to 6$ mit dem nutzbaren Fluss 5 ausgewählt.

Anschließend wird der Fluss aktualisiert. Im nächsten Schritt wird dann der Pfad $1\to 3\to 5\to 6$ gewählt. Ebenfalls ist hier wieder ein nutzbarer Fluss von 5.

Nach der zweiten Aktualisierung ist nur noch ein Pfad vom Start zum Ziel möglich. Also wird der Pfad $1\to 3\to 2\to 4\to 6$ ausgewählt. Dieser Fluss enthält allerdings nur noch einen nutzbaren Fluss von 4.

Nach dem Aktualisieren des Flusses ist es nicht mehr möglich einen Pfad vom Start zum Ziel zu finden. Damit ist die Berechnung beendet. Wie zuvor berechnet ist der maximale Fluss 14.

Problem: Ungünstige Pfadwahl

Die bisher betrachtete Version des Algorithmus ist nicht immer optimal.

Wählen der Pfad $1\to 3\to 2\to 4$ ausgewählt, besitzt dieser Pfad einen nutzbaren Fluss von 5.

Nun wird der Fluss aktualisiert. Daraus folgt, dass keine weitere Pfadwahl mehr möglich ist. Dabei wäre die optimale Lösung über die Pfade $1\to 2\to 4$ und $1\to 3\to 4$.

Das Problem ist, dass der Fluss nicht zurückgenommen werden kann. Die Lösung dazu ist, dass man entgegengesetzte Flussrichtung durch Rückkanten erlaubt. Auch hier wird wieder der ungünstige Pfad $1\to 3\to 2\to 4$ mit einem nutzbaren Fluss von 5 im ersten Schritt ausgewählt.

Anschließend wird der Fluss aktualisiert. Dabei wird der Pfad $1\to 2\to 3\to 4$ mit dem nutzbaren Fluss von 5 ausgewählt.

Beim erneuten aktualisieren des Flusses, stellt sich heraus, dass keine weiteren Pfade möglich sind. Damit ist die Berechnung, bei einem maximalen Fluss von 10, beendet.

Analyse

Terminierungstheorem

Sind alle Kapazitäten in G nicht-negativ und rational, dann terminiert der Algorithmus von Ford‐Fulkerson nach endlicher Zeit.

Laufzeittheorem

Ist X der Wert eines maximales Flusses in G=(V,E) und sind alle Kapazitäten in G nicht-negativ und ganzzahlig, so hat der Algorithmus von Ford‐Fulkerson eine Laufzeit von O(|E|X). 

Korrektheitstheorem

Sind alle Kapazitäten in G nicht‐negativ und rational, dann berechnet der Algorithmus von Ford‐Fulkerson den Wert eines maximalen Flusses.

Anmerkung

Die Wahl des Pfades beeinflusst die Anzahl benötigter Iteratoren. Bei dem Verfahren von Edmons und Karp muss die Anzahl der Pfade die in einem Graphen G = (V,E) bis  zum Finden des maximalen Flusses verfolgt werden, kleiner sein als |V||E|, wenn jeweils der kürzeste  Pfad von Quelle q zu Ziel z gewählt wird. Daher kann die Auswahl des nächsten kürzesten Pfades basierend auf einer Variante der Breitensuche erfolgen. Dadurch wird die Laufzeit auf $O(\mid V\mid \mid E{\mid }^2)$ verbessert.