Dinic algorithm
The Dinic or Dinitz algorithm is based on two notions: a graph level, and a blocking flow (level graph & blocking flow).
To determine the level graph, we place the source at level 1, its successors at level 2, and so on.
The blocking flow is the maximum flow can pass in a given path.
Dinic's algorithm is as follows:
- build a level graph
- find an increasing path (the smallest) from the source to the well
- find the arc limiting the increasing path
- find a path increasing from limiting summit to the well
- repeat steps 3 and 4 to build a blocking flow until there is no longer an increasing path
Example
Construction of the level graph:
Find an increasing path, find the limiting arc:
Return to step 3 and 4:
And so on until no longer finding an increasing path:
EN 
FR 
ES