Algorithmus von Ford und Fulkerson
Der Algorithmus von Ford und Fulkerson (nach seinen Erfindern L._R._Ford und D._R._Fulkerson) dient der Berechnung eines maximalen_Flusses in einem Netzwerk.
Algorithmus
N bezeichnet das Netzwerk mit q als Quelle und s als Senke.
Nach Ende des Algorithmus enthält Fluss den maximalen Fluss.
Fluss = leerer Fluss
N' = N
solange es in N einen Weg P von q nach s gibt
erweitere Fluss mit einem Fluss über P
N = der Residualgraph von N und Fluss
Existiert im Residualgraphen ein Weg zwischen Quelle und Ziel , so nennen wir diesen augmentierenden Pfad (augmenting path). Dieser aus Residualkanten bestehende Pfad gibt einen weiteren möglichen Fluss an, der im Algorithmus von Ford und Fulkerson zur Verbesserung des maximalen Flusses genutzt wird. Erst wenn keine augmentierenden Pfade mehr existieren, wurde ein maximaler Fluss ermittelt.
Zeitkomplexität
Die Komplexität des Algorithmus ist abhängig von der Anzahl der Kanten m und der Anzahl der Knoten n. Obwohl jeder Schleifendurchlauf des Algorithmus lediglich O(m) Zeit benötigt (siehe Landau-Notation), ist er bei ungünstiger Wahl des flusserweiternden Weges P vom maximalen Fluss abhängig.
Für irrationale Kapazitäten konvergiert der Algorithmus mitunter nicht oder nicht unbedingt gegen den richtigen Wert.
Wenn in jedem Augmentierungsschritt der jeweils kürzeste s-t-Pfad gewählt wird, verkürzt sich die Laufzeit auf O(n · m2)). Dies ist der Fall, wenn die flusserweiternden Wege über Breitensuche gefunden werden.
Siehe auch
Algorithmus von Edmonds und Karp
Flüsse und Schnitte in Netzwerken
Weblinks
• Ein sehr anschauliches Applet zu Ford-Fulkerson und Dijkstra.
