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
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: