Ford Fulkerson KE1 Beispiel 4.5 Seite 82
Hallo,
ich habe versucht mir den Ford Fulkerson Algortihmus an Hand des Beispiels 4.5 KE 1 auf Seite 81/82 zu verinnerlichen. Der erste Iterationschritt ist mir noch klar, bei Iteration 2 hackt es dann: Ist (1+,3) bei Knoten 3 nun eine Erhöhung, oder Erniedrigung der Flusses um 3? Oder der tats Fluss (wovon ich mal ausgehe). Wieso fliessen dann nach Knoten 2 (3+,3). Oder das quasi die verwertbare Restkapazität? Ich komm einfach nicht drauf.
Danke für die Hilfe
Grüße
NERD
Comments
skdo
Contributions on this page: 1
View profileNerd,
die Markierung (1+, 3) bei Knoten 3 entstand, weil es möglich ist, von Knoten 1 aus 3 Einheiten mehr zum Knoten 3 zu transportieren als dies nach Iteration 1 der Fall war.
Die Markierungen musst du nach Abschluss der Iteration, also wenn der Knoten s = 6 markiert werden konnte, rückwärts lesen und den Fluss dann jeweils erhöhen.
Gruß,
Sabine.
NERD
Contributions on this page: 2
View profileOk, vielen Dank für die Antwort. Ich denke, ich habe es jetzt verstanden