[DSAL] Maximaler Fluss

[aRo]

Hallo!

Irgendwie habe ich noch im Kopp, dass Herr Habbecke gesagt hat, dass man den flussvergrößernden Weg nach irgendeinem Kriterium wählen muss, damit der Beweis, den wir geführt haben klappt, oder sowas.

Kann es sein, dass man immer den Weg nimmt, der nach Breitensuche am kürzesten ist? Und wenn zwei Wege gleich lang sind, darf man es sich aussuchen?

edit: hm, ja, es scheint mir bei dem Beweis der Laufzeit eine Rolle zu spielen.

Meint ihr wir müssen die Beweise können?
Wie handhabt ihr das mit dem ganzen Gedöns von wegen Inside Test und so?

[Stasik]

Bei der Tifensuche hast du pseudopolinomielle Laufzeit, d.h. die Anzahl der Iterationen ist in den Kapazitäten der Kanten begrenzt.
Bei der Breitensuche wergen immer die kürzesten fv Wege gefunden und die Laufzeit von Ford-Furkelson O(n^5), weil sich die Entfernungen der Knoten von der Quelle vergrößern.

[TheStranger]

Haben die Flussalgorithmen auch in Effiziente Algorithmen durchgenommen, kannst also auch ma da in den Folien schaun.

Klick mich

Auf Seite 10 ff. (bzw. 5 / 21) wird der Algorithmus von Edmonds und Karp erklärt und gezeigt, warum damit Ford Falkerson mit Breitensuche nur braucht.