Dinic algorithm

The Dinic or Dinitz algorithm is based on two notions: a level graph and a blocking flow.

To determine the level graph, we set the source to level 1, its successors to level 2, and so on.


The blocking flow is the maximum flow that can pass through a given path.


Dinic’s algorithm is as follows:

  1. to build a level graph
  2. to find an increasing path (the smallest) from the source to the sink
  3. to find the arc limiting the path increasing
  4. to find a increasing path from limiting arc towards the sink
  5. to repeat steps 3 and 4 to build a blocking flow until there is no longer an increasing path


Building the level graph:


To find an increasing path, find the limiting arc:


Back to step 3 and 4:


And so on until you no longer find an increasing path: