Eingabe: Netzwerk N, Ausgabe: ein Fluß f für N.
-
f0 = (e 0).
- Solange fi einen vergrößernden Weg P gestattet,
setze
fi + 1 = fi.
- sonst gibt fi aus
Satz: In Netzwerken mit ganzzahligen Kapazitäten
ist der maximale Fluß ganzzahlig
und wird nach endlich vielen Schritten durch diesen Algorithmus gefunden.
Bemerkungen:
- Algorithmus terminiert, aber rechnet evtl. lange
- für irrationale Kapazitäten ist noch nicht einmal Termination garantiert!
Johannes Waldmann
2005-01-25