Diese Frage bezieht sich auf die zeitliche Komplexität des Ford-Fulkerson-Maximalflussalgorithmus, wenn DFS zum Auffinden von Erweiterungspfaden verwendet wird.
Es gibt ein bekanntes Beispiel, das zeigt, dass man mit DFS eine lineare Anzahl von Iterationen im maximalen Fluss benötigen kann, siehe zum Beispiel die oben verlinkte Wikipedia-Seite.
Dieses Beispiel überzeugt mich jedoch nicht wirklich: Eine Standard-DFS-Implementierung würde nicht das Verhalten aufweisen, zwischen B und C als erstem Knoten des Pfads zu wechseln (unter Verwendung der Scheitelpunktnamen von der Wikipedia-Seite).
Setzen wir also die sehr natürliche Bedingung auf, dass die DFS bei jedem Besuch eines Knotens die Nachbarn von in derselben Reihenfolge untersucht. Gibt es noch Beispiele, für die FF mit DFS eine große Anzahl von Iterationen verwendet?u
Als Variante nehmen wir an, dass wir die zusätzliche Eigenschaft haben, dass die unterschiedlichen Anordnungen der Nachbarn mit einer willkürlichen, aber festen globalen Anordnung der Eckpunkte übereinstimmen. Macht das einen Unterschied?
Dies scheint mir eine ziemlich grundlegende Frage zu sein; Ich entschuldige mich im Voraus, wenn die Antwort bekannt ist, aber ich bin kein Experte für Strömungen und ein bisschen googeln hat nichts ergeben.
Edit: Die Antwort lautet ja, es gibt noch Beispiele. Siehe Abbildung 2 dieses Dokuments . In diesen Beispielen nimmt FF mit DFS eine exponentielle (in der Anzahl der Eckpunkte) Anzahl von Iterationen an. Es scheint leicht zu beweisen, dass dies eng ist, dh dass die Anzahl der Iterationen immer durch (unabhängig von den Werten der Kapazitäten).
quelle
Antworten:
Wenn Adjazenzlisten im Voraus festgelegt wurden, endet die DFS immer (auch wenn irrationale Kapazitäten vorhanden sind).
Siehe Dean, Goemans, Immorlica - Endliche Beendigung von "Augmenting Path" -Algorithmen in Gegenwart irrationaler Problemdaten .
quelle