Blocking flow by Dinic

General information

Algorithmic problem: Blocking flow.

Type of algorithm: loop.

Abstract view

Invariant: The current flow is feasible.

Variant: The number of saturated arcs increases.

Break condition: There is no more flow-augmenting ordinary [math]\displaystyle{ (s,t) }[/math]-path in [math]\displaystyle{ G }[/math] (that is, all arcs on the path are forward arcs).