Dinic

General Information

Algorithmic problem: Max-Flow Problems

Type of algorithm : loop.

Abstract View

Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations: The flow [math]\displaystyle{ f }[/math] is feasible. If all upper bounds are integral, the [math]\displaystyle{ f }[/math]-values are integral as well.

Variant: The smallest number of arcs on a flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path strictly increases.

Induction basis

Abstract view: Initialize [math]\displaystyle{ f }[/math] as an arbitrary feasible flow, for example, the zero flow.

Proof: Nothing to show.