Edmonds-Karp Algorithmus < Algorithmen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:19 Sa 13.02.2010 | | Autor: | koker |
Hallo Leute,
ich hab eine Frage zum Algorithmus von Edmonds-Karp.
Ich weiss zwar, was der Algoritmus liefert(maximalen Wert in einem s-t Fluss) jedoch kann ich mir das nicht erklären wie der maximale Fluss durch den Einsatz von augmentierenden Pfaden rausgefunden werden kann.
Könnte mir einer von Euch evtl. hier weiterhelfen?(brauche das für meine mündliche Prüfung am Montag ;))
Schöne Grüße,
koker
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:16 Di 16.02.2010 | | Autor: | bazzzty |
> ich hab eine Frage zum Algorithmus von Edmonds-Karp.
> Ich weiss zwar, was der Algoritmus liefert(maximalen Wert
> in einem s-t Fluss) jedoch kann ich mir das nicht erklären
> wie der maximale Fluss durch den Einsatz von
> augmentierenden Pfaden rausgefunden werden kann.
Hallo,
vielleicht solltest Du solche Fragen nicht erst auf den letzten Drücker stellen, die meisten schauen hier vielleicht nicht ständig (und nicht immer am Wochenende) rein.
Zu Deiner Frage: Der Edmonds-Karp-Algorithmus bestimmt nicht nur den Wert eines maximalen s-t-Flusses, sondern auch einen maximalen s-t-Fluss selbst. Das ist schon das ganze Geheimnis. Man nimmt einen Fluss (zu Beginn einen "leeren" Fluss, bei dem über keine Kante etwas fließt), und versucht, ihn zu erhöhen. Eine Flusserhöhung geschieht entlang eines augmentierenden Pfades, was nichts anderes ist als ein Pfad aus vorwärtsgerichteten Kanten, die noch zusätzlichen Fluss zulassen und rückwärtsgerichteten Kanten, die schon echten Fluss tragen, den man "zurückdrücken" kann.
Man nutzt dafür die schöne Aussage, dass es zu einem nicht-maximalen Fluss immer einen erhöhenden Pfad gibt.
Wenn Du mehr wissen willst, musst Du etwas klarer zusammenfassen, was Du verstehst, und was nicht. Als Tipp: Wenn Du Dir den Eintrag zum
![[]](/images/popup.gif) Ford-Fulkerson-Algorithmus bei Wikipedia anschaust (vor allem das Beispiel), siehst Du alles wesentliche. Edmonds und Karp haben nur festgestellt, wie man beim FF-Algo erhöhende Pfade suchen sollte, um die Laufzeit zu verbessern.
|
|
|
|
