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.

dinic1

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

dinic2

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

Example

Building the level graph:

dinic3

To find an increasing path, find the limiting arc:

dinic5

Back to step 3 and 4:

dinic6

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

dinic7

Publicités