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




Ford-FulkersonBearbeiten

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

Berechnung des maximalen FlussesBearbeiten

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.

AlgorithmusBearbeiten

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

BeispieleBearbeiten

Wir haben einen Graph mit Kapazitäten gegeben





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





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   Der nutzbare Fluss beträgt 4.




Der Fluss wird aktualisiert. Die Auswahl des Pfades ist nun :  . Der nutzbare Fluss beträgt 5.






Der Fluss wird aktualisiert. Die Auswahl des Pfades ist nun :  . Der nutzbare Fluss beträgt 3.






Der Fluss wird aktualisiert. Die Auswahl des Pfades ist nun :  . Der nutzbare Fluss beträgt 2.







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   mit dem nutzbaren Fluss 5 ausgewählt.

Anschließend wird der Fluss aktualisiert. Im nächsten Schritt wird dann der Pfad   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   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 PfadwahlBearbeiten

Die bisher betrachtete Version des Algorithmus ist nicht immer optimal.

 

Wählen der Pfad   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   und  .

 

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   mit einem nutzbaren Fluss von 5 im ersten Schritt ausgewählt.

 

Anschließend wird der Fluss aktualisiert. Dabei wird der Pfad   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.

AnalyseBearbeiten

TerminierungstheoremBearbeiten

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

LaufzeittheoremBearbeiten

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). 

KorrektheitstheoremBearbeiten

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

AnmerkungBearbeiten

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   verbessert.