Algorithmus von Ford und Fulkerson
aus Wikipedia, der freien Enzyklopädie
| Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf bitte mit ihn zu verbessern und entferne anschließend diese Markierung. |
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.
Inhaltsverzeichnis |
[Bearbeiten] 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
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
[Bearbeiten] 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.
